정수 삼각형

백준 1932

방법1. 동적 계획법

import sys

n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

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

print(max(arr[n-1]))

이 문제는 RGB문제를 풀고, 동적계획법은 이렇게 푸는구나를 알고 나니 어렵지 않게 풀 수 있었다.
핵심은 1행->2행 2행->3행 .. 이렇게 생각하는게 아니라,
2행->1행 3행->2행 .. 이렇게 생각하는 것이다.
2행을 기준으로 1행을 어떤 걸 선택할 때 어떤 값이 나오는지를 저장한다.