[BOJ] [Python] 1932번 : 정수 삼각형

수기로 풀어보기

 

 

li 리스트와 동일한 위치의 dp 리스트 위치에는, 그 위치까지 계산된 값을 넣었다.

 

num = int(input())

li = []
dp = []

for n in range(num):
    li.append(list(map(int, input().split())))

    if(n != num-1):
        dp.append([0] * len(li))

dp.append(li[-1])

li.reverse()
dp.reverse()

for i in range(num):
    for j in range(len(li[i])-1):
        dp[i+1][j] = max(dp[i][j], dp[i][j+1]) + li[i+1][j]

print(dp[-1][0])