백준 1932번: 정수 삼각형 [실버 1] - Python

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

1932번: 정수 삼각형

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

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

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

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

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

알고리즘 분류

다이나믹 프로그래밍

 

풀이

문제를 보는 순간 다이나믹 프로그래밍으로 푸는 문제다!라는 것이 눈에 보이는 문제였습니다. 대신 어떻게 적용할지는 조금 생각을 해봐야 했네요. 다음과 같은 아이디어로 접근했습니다.

 

1. 삼각형 형태의 DP 테이블을 2차원 리스트로 생성한다.
2. 맨 꼭대기 수를 DP 테이블의 꼭대기에 저장한다.
3. 내려오면서 선택한 수들의 합이 최대가 되려면 내려갈 때 지금까지의 경로 중에서 가장 합이 큰 경로를 통해 내려가야 한다. 즉 아래층에 있는 수에 내려갈 때에는 왼쪽 위에서 내려올지, 오른쪽 위에서 내려올지를 판단해서 합이 더 큰 쪽을 선택해 내려온다. DP 테이블에서 더 큰 쪽을 선택하면 된다. 가장자리에 위치한 수는 선택지가 하나 뿐이므로 바로 위에 있는 수에서 그냥 내려온다.
4. 내려온 수와 지금까지 경로의 수들의 합을 DP테이블에 추가해 준다.

문제에서 주어진 예시를 통해 이해해 보자구요. 먼저 꼭대기에 있는 7은 경로가 자기 자신뿐이므로 자기 자신인 7을 DP테이블에 넣습니다.

#예제 삼각형
        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

#DP테이블
7

다음으로 2행에 있는 3과 8은 가장자리에 위치해 있기 때문에, 위에서 내려올 수 있는 선택지가 7에서 내려오는것 뿐입니다. 그래서 7에서 내려오고, DP테이블에 7+3=10, 7+8=15를 각각의 자리에 저장해 줍니다.

#DP테이블
7
10 15

그다음으로 3행을 보면, 8과 0은 역시 가장자리에 있어서 선택지가 하나뿐이니 그냥 내려옵니다. 각각 10+8=18, 15+0=15을 DP테이블에 추가해 주면 됩니다. 하지만 1은 왼쪽 위에서 내려올지, 오른쪽 위에서 내려올지를 선택할 수가 있습니다. 이 경우에는 무엇을 선택하는 것이 경로의 합이 최대가 될까요? 오른쪽 위인 15에서 내려오는 것이 최대가 됩니다. 따라서 DP 테이블의 1 위치는 15+1=16을 넣어줍니다.

#DP테이블
7
10 15
18 16 15

이를 반복해 주면 되는 것입니다! 코드로 확인해 봅시다.

 

import sys

input = sys.stdin.readline

n = int(input())

triangle = []
for i in range(n):
    triangle.append(list(map(int, input().split())))

dp = [[] for _ in range(n)]

dp[0].append(triangle[0][0])

for i in range(1, n):
    for j in range(len(triangle[i])):
    	#가장자리이면 그냥 내려오기
        if j == 0:
            dp[i].append(triangle[i][j] + dp[i - 1][j])
        elif j == len(triangle[i]) - 1:
            dp[i].append(triangle[i][j] + dp[i - 1][j - 1])
        #가장자리가 아니면 어느곳에서 내려올지 선택해야함
        else:
            dp[i].append(max(triangle[i][j] + dp[i - 1][j - 1], triangle[i][j] + dp[i - 1][j]))

print(max(dp[n - 1]))

여담으로 그냥 DP테이블을 만들지 않고 그냥 삼각형의 각 자리를 DP테이블처럼 쓰면서, 숫자를 갱신하면서 문제를 풀 수도 있습니다. 그렇게 하는 것이 오히려 이해도 더 쉽고 코드도 더 짧아질 것 같네요. 하지만 다른 문제에서는 삼각형을 훼손하면 안 되는 문제가 나올 수도 있는 것이고, 저희는 공부하는 입장이니까 일단 정석적으로 DP 테이블을 이용해 문제를 푸는 것으로 합시다~!