[동적 계획법] 정수 삼각형

1932번: 정수 삼각형

저번 문제와 마찬가지로 DP 테이블을 이용해서 쉽게 풀 수 있었다.

 

from sys import stdin

N = int(stdin.readline())

L = []

while True:
    line = list(map(int, stdin.readline().split()))

    if len(L) == 0:
        L.append(line)
    else:
        prev = L[len(L) - 1]
        next_line = []

        for i, v in enumerate(line):
            if i == 0:
                next_line.append(v + prev[0])
            elif i == len(prev):
                next_line.append(v + prev[len(prev) - 1])
            else:
                next_line.append(v + max(prev[i - 1], prev[i]))

        L.append(next_line)

    if len(L) == N:
        break

print(max(L[len(L) - 1]))