백준 1932번: 정수 삼각형 (Python)

접근

백준 단계별 풀이 순서로 풀고 있다면 바로 이전 문제인 1149번: RGB 거리와 매우 유사하게 풀 수 있다.

2021.03.27 - [SW/백준 (Python)] - 백준 1149번: RGB 거리 (Python)

백준 1149번: RGB 거리 (Python)

제시된 삼각형과 같은 모습을 한 리스트를 작성하여, 해당 칸에는 해당 칸까지의 길 중 최대값을 입력하는 방법으로 해결할 수 있다. 점화식은 아래와 같다.

max_route[i][j] = max(max_route[i-1][j-1], max_route[i-1][j]) + triangle[i][j]

계산이 완료 된 후, max_route 리스트의 max 값이 최대값이 되는 길의 값임을 알 수 있다.

코드

import sys


n = int(sys.stdin.readline())
triangle = [[0] * (n + 1) for _ in range(n)]
max_route = triangle[:]
for i in range(n):
    m = list(map(int, sys.stdin.readline().split()))
    for j in range(len(m)):
        triangle[i][j + 1] = m[j]
max_route[0] = triangle[0]
for k in range(1, n):
    for l in range(1, n + 1):
        max_route[k][l] = max(max_route[k - 1][l - 1], max_route[k - 1][l]) + triangle[k][l]
print(max(max_route[-1]))

더 생각해 볼 것?

...