백준 1932번: 정수 삼각형 (파이썬)

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번째 줄까지 정수 삼각형이 주어진다.

 

출력

 

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

 

풀이

 

문제를 읽고 DP로 해결해야 하는 문제라고 생각했다.

dp 리스트는 r행 c열까지 선택된 수의 합의 최댓값을 저장하는 리스트다. 0행 0열은 당연히 정수 삼각형의 가장 꼭대기에 있는 값을 사용해야 한다. r >= 1에 대해서 r행 c열의 값은 대각선 왼쪽, 대각선 오른쪽에서 내려온 값 중 큰 값을 선택해야 한다. 예를 들어, 2행 2열의 값은 1행 1열, 1행 2열에서 내려온 값과 비교해야 한다는 것이다. 이때 각 행의 첫 열과 마지막 열은 각각 대각선 왼쪽, 대각선 오른쪽에서 내려올 수가 없다. 이 점을 고려하여 코드를 작성해 주었다.

이후 가장 마지막 행에서 가장 큰 값을 선택하면 문제를 해결할 수 있다.

 

소스 코드

import sys

n = int(sys.stdin.readline())

tri = []
for _ in range(n):
  tri.append(list(map(int, sys.stdin.readline().split())))

dp = [[0]*i for i in range(1, n+1)]
dp[0][0] = tri[0][0]

for i in range(n-1):
  for j in range(i+1):
    dp[i+1][j] = max(dp[i][j] + tri[i+1][j], dp[i+1][j])
    dp[i+1][j+1] = max(dp[i][j] + tri[i+1][j+1], dp[i+1][j+1])

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