[백준] 1932: 정수 삼각형 - 동적계획법

다른 코드 참조: O, 푼 횟수: 4

풀이과정

먼저 위의 문제와 같은 삼각형이 주어졌다고 가정할 때, 반복문을 이용해 최댓값을 구한다면

1. 7-3-8-2-4

2. 7-3-8-2-5

3. 7-3-8-7-5

...

16. 7-8-0-4-5

이런식으로 전개되고 1~3에서와 같이 7-3-8 이 계속해서 반복되는 비효율이 발생한다. 따라서 동적 계획법을 이용해야 한다.

 

먼저, t[r][c] = 삼각형 r번째 줄, c번째 칸,    dp[i][k] = t[i][k]까지의 합의 최댓값이라고 하자.

데이터가 추가된다고 할 때, 그 데이터에 도달할 수 있는 데이터는 다음과 같은 경우가 있다.

만약 삼각형의 양쪽 끝쪽 데이터의 경우(i번째 줄 0번 칸 or i번칸)를 제외하고 본다면, 추가되는 칸까지의 최대합은 dp[i-1][k-1]과 dp[i-1][k]중 큰 값과 추가되는 데이터를 더한 값이다. (dp[i][k] = max(dp[i-1][k-1], dp[i-1][k]) + t[i][k])

그리고 양쪽 끝쪽 데이터는 그 이전칸까지의 합에서 추가되는 데이터를 더하면 된다.

 

코드

import sys

n = int(sys.stdin.readline())
t = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
dp = [[0 for i in range(n)] for i in range(n)]

for i in range(n):
    for ii in range(i+1):
        if i == 0:
            dp[0][0] = t[0][0]
        elif ii == 0:
            dp[i][0] = t[i][0] + dp[i-1][0]
        elif ii == i:
            dp[i][ii] = t[i][ii] + dp[i-1][ii-1]
        else:
            dp[i][ii] = t[i][ii] + max(dp[i-1][ii-1], dp[i-1][ii])

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