백준 1932 : 정수 삼각형 (Python)

백준 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

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

예제 출력 1

30

---

나의 풀이

• 이 문제를 완탐으로 풀이한다고 생각해보면 경로의 비용을 계산할 때 중복되는 연산이 매우 많을 것이다. 따라서 이 문제는 DP 테이블을 만들어두고 중복되는 계산값을 저장해 시간복잡도를 줄이는 전형적인 DP 문제이다. 자신의 대각선 왼쪽 또는 대각선 오른쪽 원소만을 다음 경로로 선정할 수 있다는 조건이 존재하기에 tri[i][j]는 다음 경로로 tri[i+1][j] 또는 tri[i+1][j+1]만을 선택할 수 있다. 따라서 정수 삼각형과 동일한 크기의 DP 테이블을 만들어두고 노드별 최대값 비용을 계속 업데이트 해주도록 코드를 구현하면 된다. 단, tri[i+1][j+1]은 이전 노드가 tri[i][j] 또는 tri[i][j+1] 일 수 있기에 더 큰 값을 비교해 테이블을 업데이트 한다. 예제 입력 1의 DP 테이블을 모두 업데이트하면 아래 그림과 같은 모양의 테이블이 만들어진다.

import sys 

input = sys.stdin.readline

answer = 0 

n = int(input())
tri = [list(map(int,input().split())) for _ in range(n)]
dp = [[tri[i][j] for j in range(i+1)] for i in range(n)]


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[-1]))