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

문제

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

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

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

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

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

정답 코드

import sys

n = int(sys.stdin.readline().strip())
triangles = []
triangles.append([0])
for i in range(n):
  triangles.append(list(map(int, sys.stdin.readline().strip().split())))

## dp 테이블 = 삼각형 모양으로 현재까지의 최댓값이 무엇인지 담을 수 있도록 만들기
dp = [[0] * i for i in range(len(triangles))]
dp[0] = [0]

for i in range(1, n + 1):
  ## dp 테이블에 저장하기
  for idx, value in enumerate(triangles[i]):
    if idx == 0:
      dp[i][idx] = dp[i - 1][idx] + value
    elif idx == len(triangles[i]) - 1:
      dp[i][idx] = dp[i - 1][idx - 1] + value
    else:
      dp[i][idx] = max(dp[i - 1][idx - 1] + value, dp[i - 1][idx] + value)

print(max(dp[-1]))

문제 해결 접근

• 계속 DP만 풀다보니까 이런 문제 유형은 DP로 풀어야 하는 구나, 하는 감은 생겼다.
• 처음에는 트리의 각 레벨별로 최댓값을 dp테이블에 저장하여 풀면 되는건가? 했는데
• 여기서 핵심 아이디어는 dp 테이블도 삼각형 모양으로 만들어서, 각 자리의 값이 위의 레벨들을 모두 고려하였을 때의 최댓값이 저장되도록 알고리즘을 짜는 것이었다.
• 해당 아이디어를 생각하고 나서는 생각지 못한 반례가 나오지는 않아서 그나마 괜찮았다.