[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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

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))