1932 정수삼각형

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

N = int(read())
graph = []
for _ in range(N):
    graph.append(list(map(int,read().split())))

dp_table = [[0 for _ in range(N)] for _ in range(N)]
dp_table[0] = graph[-1]
for i in range(1,N):
    for j in range(N-i):
        dp_table[i][j] = max(graph[N-1-i][j]+dp_table[i-1][j],
                             graph[N-1-i][j]+dp_table[i-1][j+1])

print(dp_table[-1][0])

3. 문제 풀이

생각보다 문제가 간단하다. 이제 슬슬 다이나믹 프로그래밍의 바텀업 방식에 대해 익숙해지는 것 같다.

1. 삼각형의 제일 아래라인을 dp table에 넣어서 초기화 한다.
2. for문을 돌면서 그래프의 마지막의 바로 윗 row의 값들을 dp table의 좌우 대각선 값과 더하면서 max값을 찾고 dp table에 넣어주면 된다. 점화식은 다음과 같다.

\[dp\_table[i][j] = max(graph[N-1-i][j]+dp\_table[i-1][j], \\ graph[N-1-i][j]+dp\_table[i-1][j+1])\]