[CLASS 4]백준 1932번 - 정수 삼각형

1932번 : 정수 삼각형

 

항상 생각하는 것이지만, DP문제는 처음에 풀 때 머리가 참 아픈데 풀고 나면 이걸 왜 못하고 있었을까 라는 생각이 든다.

 

이 문제는 약간 고정관념이 있으면 풀기 힘든 것 같다. 피라미드를 꼭대기부터 브루트포싱으로 모든 경로를 탐색하며 푼다면 무조건 시간 초과가 뜬다. 내가 바로 처음에 이짓을 했다.

 

내 코드(시간 초과):

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline

def triangle(h,k):
    if h != n:
        if h:
            if k == h:
                ans[h][k] = ans[h-1][k-1] + t[h][k]
            elif k == 0:
                ans[h][k] = ans[h-1][k] + t[h][k]
            else:
                ans[h][k] = max(ans[h-1][k-1],ans[h-1][k]) + t[h][k]
        
        triangle(h+1,k)
        triangle(h+1,k+1)

n = int(input())
t = [list(map(int,input().split())) for _ in range(n)]
ans = [[0]*(i+1) for i in range(n)]
ans[0] = t[0]

triangle(0,0)
print(max(ans[-1]))

 

안될 껄 거의 확실히 알고 있었지만... 그래도 한번 제출해 보았으나 역시나 시간 초과에 걸렸다.

 

그리고 나서 DP를 통해 풀어야 하겠다는 것을 깨닫고 DP테이블을 만들어 보려고 하지만 꼭대기에서부터 어떻게 만들지 도저히 감이 잡히질 않았다. 한참 고민하다 아래층에서부터 올라가볼까? 라는 생각을 하자마자 정답처리를 받을 수 있었다.

 

내 코드:

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline

n = int(input())
t = [list(map(int,input().split())) for _ in range(n)]

for h in range(n-2,-1,-1):
    for i in range(h+1):
        t[h][i] += max(t[h+1][i],t[h+1][i+1])

print(t[0][0])

 

피라미드의 가장 아래 바닥부터 위로 올라가면서 바로 아래 층 왼쪽 혹은 오른쪽 대각선에서 보다 큰 수를 더한다. 이런 식으로 거꾸로 올라가면 최상층에서는 결국 가장 큰 값이 저장되게 된다.