(Python) - BOJ(1932번) : 정수 삼각형

 

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

1932번: 정수 삼각형

---

• 해설 : 

정수로 이루어진 삼각형의 맨 위부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 문제이다.

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

 

 

 

---

• 풀이 :

DP를 사용하면 풀 수 있다. 아래층의 수를 선택할 때 그 합이 최소가 되는 값으로 갱신해주면 된다.

 

 

 

---

• 소스코드 : 

 

import sys
input = sys.stdin.readline
 
if __name__ == "__main__":
    N = int(input())
    if N == 1:
        print(int(input()))
        exit()
    cost = [[int(input())]]
    for _ in range(N-1):
        cost.append(list(map(int,input().split())))
    dp = [[] for _ in range(N+1)]
    dp[1] = [cost[0][0]+cost[1][0],cost[0][0]+cost[1][1]]
    for i in range(2,N):
        for j in range(i+1):
            if j==0:
                dp[i].append(dp[i-1][j]+cost[i][j])
            elif j==i:
                dp[i].append(dp[i-1][-1]+cost[i][j])
            else:
                dp[i].append(max(dp[i-1][j-1]+cost[i][j],dp[i-1][j]+cost[i][j]))
    print(max(dp[N-1]))