[Python] 백준 #1932 정수 삼각형

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

1932번: 정수 삼각형

[ 알고리즘 ]

DP

 

[ 문제 접근 ]

▶ 완전탐색의 구조인데? 경우의 수가 너무 큰데? 메모이제이션 가능하다 ! 매번 최대를 구해야하는 겹치는 부분문제

= DP

 

01. 입력

7 ->tri[0][0]

3 8 -> tri[1][0], tri[1][1]

8 1 0 -> tri[2][0] ,tri[2][1],tri[2][2]

2 7 4 4 ...

4 5 2 6 5 ...

 

02. 상태값

n행의 m열 -> dp[n][m]

 

03. 조건

1. tri[n][m] 이 해당 줄의 시작일 땐, dp[n][m] = dp[n-1][m] + 현재위치의 값

2. tri[n][m] 이 해당 줄의 마지막일 땐, dp[n][m] = dp[n-1][m-1] + 현재위치의 값

3. 그외.. 중간에 껴있는 것들 일땐, dp[n][m] = max( dp[n-1][m], dp[n-1][m-1] ) + 현재 위치의 값

 

[ 코드 ]

n = int(input())
dp=[[0]*n for _ in range(n)]
tri = []

for _ in range(n):
    tri.append(list(map(int, input().split())))

dp[0][0]=tri[0][0]
for i in range(1, n):
    List = tri[i]
    for j in range(len(List)):
        if j == 0:  # 첫번째 값
            dp[i][j]=dp[i-1][j]+List[j]
        elif j==len(List)-1: # 마지막 값
            dp[i][j]=dp[i-1][j-1]+List[j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+List[j]

Max=dp[n-1][0]
for i in range(1,n):
    if Max<dp[n-1][i]:
        Max=dp[n-1][i]
print(Max)