문제

입력

출력

예시 입출력

풀이

해당 문제에 주어진 삼각형의 제일 아래층 부터 위로 거꾸로 거슬러 올라가며 최대값이 나오게끔 하는 경로를 구하였다. 마지막에서 두번째 층부터 차례로 값들을 저장했다. 어떤 값을 저장했냐면, 바로 다음 층에서 고를 수 있는 두가지 경우 중 큰 값을 골랐을 때를 기준으로 현재 층과의 합이다 그림으로 이해하면 더 편하다.

첫번째로 5의 크기를 가지는 삼각형이 주어졌을 때, 아래와 같은 동작을 수행한다.

1. 4번째 층에서 바로 밑의 5번째 층에서 고를 수 있는 최대값을 기준으로 값을 update한다. 예를들어, 4번째층의 첫번째 노드인 2에선 아래 대각선 위치에 4나 5중 5를 골랐을 때가 최대값이므로, 2+5로 해당 노드를 update한다.

2. 3번째 층에서 바로 밑의 update가 되어있는 층을 기준으로 최대값이 되게끔 update한다. 이를 반복하면, 각 노드에 대해서 해당 노드를 선택했을 때 마지막 층까지 도달하여 받을 수 있는 reward의 최대값을 계산 가능하다.

아래는 이를 코드로 구현한 것이다. DP의 핵심인 캐싱을 활용하였고, 큰 문제 (문제에 주어진 크기의 정수삼각형에서의 최대값)을 작은 문제 (소분한 작은 크기의 정수삼각형에서의 최대값)을 구하는 과정으로 나누어 해결하였고, loop문을 사용하여 bottom up (상향식)으로 문제를 해결하였다.

# 정수 삼각형
n=int(input())
num_tree=[list(map(int,input().split())) for _ in range(n)]

def func(num_tree):
    for i in range(n-1,0,-1):
        for j in range(i):
            num_tree[i-1][j]+=max(num_tree[i][j],num_tree[i][j+1])


func(num_tree)

print(num_tree[0][0])

Reference

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