[Dynamic Programming] 숫자 삼각형

https://www.acmicpc.net/problem/1932

Description

아래와 같은 숫자 삼각형이 주어질 때, 맨 위에서 아래로 이동하는 경로 중 숫자의 합이 제일 큰 경로를 찾는 문제.

7

3    8

8    1    0

2    7    4    4

4    5    2    6    5

층 수 n 과 각 층의 숫자가 주어진다. 최댓값을 구하면 된다.

Idea

2차원 list로 하면 index 처리가 간단해지지만 memory overhead가 크다. 1차원 list로 풀어보자.

총 [latex]n(n+1)/2[/latex]개의 숫자가 존재하므로,

dp <- [-1] * n(n+1)/2로 초기화한다.

각 층의 숫자는 triangle이라는 list에 저장한다.

Pseudocode

for i: 0~n-1

for j:0~i

ind = i(i+1)/2 + j

dp[ind] =

1. dp[i(i-1)/2] + triangle[ind]  ( j = 0 )
2. dp[i(i-1)/2 + j - 1] + triangle[ind] ( j = i )
3. max(dp[i(i-1)/2 + j - 1], dp[i(i-1)/2 + j]) + triangle[ind] ( j = 나머지 )

답은 max(dp[n(n-1)/2 + 0, 1, 2 ...., n]).

Code

def solve(triangle, dp, n):
    solveHelper(triangle, dp, n)
    return max([dp[n*(n-1)//2 + j] for j in range(n)])

def solveHelper(triangle, dp, n):
    dp[0] = triangle[0]

    for i in range(1, n):
        for j in range(i+1):
            ind = i*(i+1)//2 + j
            # case 1 : leftmost number of a row
            if j == 0:
                dp[ind] = dp[i*(i-1)//2] + triangle[ind]
            # case 2: rightmost number of a row
            elif j == i:
                dp[ind] = dp[i*(i-1)//2 + j - 1] + triangle[ind]
            # case 3: middle
            else:
                dp[ind] = max(dp[i*(i-1)//2 + j - 1], dp[i*(i-1)//2 + j]) + triangle[ind]

if __name__ == '__main__':
    n = int(input())

    triangle = []
    for i in range(n):
        triangle += [int(v) for v in input().strip().split()]

    dp = [-1] * (n*(n+1)//2)
    print(solve(triangle, dp, n))