[Python] 백준 1932 정수 삼각형

1932번: 정수 삼각형

다이나믹 프로그래밍 : 각 자리의 최대값은 위의 왼쪽 오른쪽 중 최댓값에 자기 자리를 더한 것이다.

 

1) 각 층별로 계산을 해야한다. 한칸 내려갈 때마다 계속 1씩 늘어나는 구조다.

2) p1과 p2에 부모의 값을 담는다.

왼쪽 부모는 맨 왼쪽 인덱스일때를 제외하고 담을 수 있고,

오른쪽 부모는 맨 오른쪽 인덱스일때를 제외하고 담을 수 있다. 

3) p1과 p2 중 큰 값 + 자신의 현재 위치값 업데이트 해주기

 

전체 코드

import sys

input = sys.stdin.readline

N = int(input())
graph = []
for _ in range(N):
    graph.extend(list(map(int, input().split())))

dp = [0 for _ in range((N + 1)* N // 2) ]
dp[0] = graph[0]
sum = 0
for i in range(1, N):
    sum += i
    for j in range(sum, sum + i + 1):
        p1 = 0 if j == sum else dp[j - i - 1]
        p2 = 0 if j == sum + i else dp[j - i]

        dp[j] = max(p1, p2) + graph[j]

print(max(dp))