[백준] 1932번 정수 삼각형 (by Python)

문제

점화식을 찾는 것은 사실 무척 쉬웠지만 인덱스를 헷갈려 시간을 낭비했다. 언제나 느끼지만 문제를 잘 푸는 것은 논리력뿐만 아니라 실수를 하지 않는 것도 포함되는 것 같다.

 

풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = []
dp = [[0] * (i + 1) for i in range(n)]
for _ in range(n):
    arr.append(list(map(int, input().strip().split())))

dp[0][0] = arr[0][0]

for i in range(1, n):
    for j in range(i + 1):
        if j == 0:
            dp[i][j] = dp[i - 1][0] + arr[i][j]
        elif j == i:
            dp[i][j] = dp[i - 1][i - 1] + arr[i][j]
        else:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j]

print(max(dp[-1]))

삼각형과 같은 모양의 메모이제이션 리스트를 만들고 각 지점마다 해당 지점까지의 최적경로의 합을 기록해두는 방식을 사용했다.