Dynamic Programming(DP) - 정수 삼각형[1932]

Idea

제일 위에서 부터 아래로 범위를 넓히면서 모든 경우의 덧셈을 더하고 최종 말단에 왔을때 최댓값을 구하면 된다.

이때, 인덱스 1부터 idx-1 까지는 더할 수 있는 수의 후보가 이전의 idx번째 수와 idx-1번째 수 총 2개가 있다.

따라서 최댓값을 구하는 문제이므로 큰 값만 뽑아서 현재 idx번째 수에 더해주면 된다.

N = int(input())
fibo = []
for i in range(N):
    nList = list(map(int, input().split()))
    fibo.append(nList)

for fidx in range(1, N):
    for idx in range(len(fibo[fidx])):
        if idx == 0:
            fibo[fidx][idx] += fibo[fidx-1][0]
        elif idx == len(fibo[fidx])-1:
            fibo[fidx][idx] += fibo[fidx-1][-1]
        else:
            fibo[fidx][idx] += max(fibo[fidx-1][idx-1], fibo[fidx-1][idx])

print(max(fibo[N-1]))