[백준] 1932 정수 삼각형

문제 출처: 백준 온라인 저지 (https://www.acmicpc.net/problem/1932)

 

문제 설명

🔎위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

처음 문제 예시만 봤을 땐 포화 이진트리나 힙을 생각하게 만드는 문제였다.

 

하지만 문제를 잘 읽어보면 이진트리 방식으로 수를 선택하면서 내려왔을 때 최대가 되는 수를 출력하는 다이나믹 프로그래밍 문제였다.

 

<정답코드>

import sys
input = sys.stdin.readline

n = int(input())
tree = []

for i in range(n):
    inp = list(map(int, input().split()))
    if i == 0:
        tree.append(inp)
        continue
    elif i == 1:
        tree.append(list(map(lambda x: x+tree[0][0], inp)))
        continue

    inp[0] += tree[-1][0]
    inp[-1] += tree[-1][-1]

    for j in range(1, len(inp)-1):
        inp[j] += max(tree[-1][j-1], tree[-1][j])

    tree.append(inp)

print(max(tree[-1]))

접근은 아래와 같다.

1. 리스트로 입력을 받아 2차원 리스트 형태로 저장한다.

2. 리스트에 저장하기 전, 각 원소에 대한 부모 노드 중 더 큰 값을 더하여 저장한다.

3. 0번째 리스트는 원래 값 그대로 저장하고, 1번째 리스트는 0번째 리스트의 값만 부모로 갖는다.

 

트리 구조에 대한 이해만 있다면 쉽게 풀 수 있었던 문제였던 것 같다.