[백준] 1932번 정수 삼각형 - Python

이번에 해결해 볼 문제는 백준에 있는 정수 삼각형이다.

---

문제 설명

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

문제 아이디어

• 이전에 수행했던 코드를 이후 계속 반복해서 사용하므로 다이나믹 프로그래밍으로 구현할 수 있다.
• 대각선으로 이동이 가능하므로 두 개의 점화식 구현
  • i층에서 j번째 숫자까지 최대 합 = max(i층 j+1번째 숫자까지 최대 합, i층 j+1번째 숫자 + i-1층 j번째 숫자까지 최대 합)
  • i층에서 j+1번째 숫자까지 최대 합 = max(i층 j번째 숫자까지 최대 합, i층 j번째 숫자 + i-1층 j번째 숫자까지 최대 합)

문제 해결 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * i for i in range(1, n+1)]
dp[0][0] = arr[0][0]
for i in range(1, n):
    for j in range(i):
        dp[i][j] = max(dp[i][j], arr[i][j]+dp[i-1][j])
        dp[i][j+1] = max(dp[i][j+1], arr[i][j+1]+dp[i-1][j])
print(max(dp[n-1]))

간단한 예시