[백준] 1932번(python 파이썬)

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

 

트리형태..

이런형태의 리스트로 만들 수 있다.

 

triangle[i][j]     j i	0	1	2	3	4
0	7
1	3	8
2	8	1	0
3	2	7	4	4
4	4	5	2	6	5

 

 

dp[i][j]           j i	0	1	2	3	4
0	triangle[i][j]
1	dp[i-1][ j ] + triangle[ i ][ j ]	dp[i-1][ j ] + triangle[ i ][ j ]
2	dp[i-1][ j ] + triangle[ i ][ j ]	MAX(dp[i-1][j-1], dp[i-1][ j ]) + triangle[ i ][ j ]	dp[i-1][ j ] + triangle[ i ][ j ]
3	dp[i-1][ j ] + triangle[ i ][ j ]	MAX(dp[i-1][j-1], dp[i-1][ j ]) + triangle[ i ][ j ]	MAX(dp[i-1][j-1], dp[i-1][ j ]) + triangle[ i ][ j ]	dp[i-1][ j ] + triangle[ i ][ j ]
4	dp[i-1][ j ] + triangle[ i ][ j ]	MAX(dp[i-1][j-1], dp[i-1][ j ]) + triangle[ i ][ j ]	MAX(dp[i-1][j-1], dp[i-1][ j ]) + triangle[ i ][ j ]	MAX(dp[i-1][j-1], dp[i-1][ j ]) + triangle[ i ][ j ]	dp[i-1][ j ] + triangle[ i ][ j ]

깊이로 설명하면

1. 현재 깊이의 맨 왼쪽 값 : 이전깊이의 맨왼쪽 값 + 자기자신

2. 현재 깊이의 맨 오른쪽 값 : [이전깊이][맨오른쪽 값] + 자기자신

3. 그외 :  MAX([이전 깊이][현재 index -1] , [이전 깊이][현재 index]) + 자기 자신

n = int(input())
triangle = [list(map(int, input().split())) for _ in range(n)]
dp = list()

for i in range(n):
    dp.append([0]*(i+1))

def int_triangle():
    global dp
    for i in range(n):
        for j in range(len(dp[i])):
            if i == 0:
                dp[i][j] = triangle[i][j]
            else:
                if j == 0 :
                    dp[i][j] = dp[i - 1][j] + triangle[i][j]
                elif j == len(dp[i])-1:
                    dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]
                else:
                    dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]

    return max(dp[n-1])

print(int_triangle())