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

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

https://www.acmicpc.net/status?user_id=dahun428&problem_id=1932&from_mine=1


문제 설명

N층의 정수 삼각형이 주어졌을 때, 위에서 아래로 내려오며 숫자를 하나씩 선택하여 합이 최대가 되는 경로를 찾는 문제입니다.
• 각 칸에서는 바로 아래 또는 오른쪽 아래로만 이동할 수 있습니다.
• 입력으로는 삼각형의 높이 n이 주어지고, 각 층의 정수들이 한 줄씩 입력됩니다.

⸻

예제 입력

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

예제 출력

30

예: 7 → 3 → 8 → 7 → 5 = 30이 최대 경로입니다.

⸻

문제 접근

이 문제는 대표적인 Bottom-up 방식의 DP 문제입니다.
• dp[i][j]를 i층 j번째 수까지의 최대 합이라고 정의합니다.
• dp[0][0]은 입력의 첫 번째 수로 초기화합니다.
• 이후 각 층마다,
• 왼쪽 끝 (j==0) → 이전 층의 같은 열
• 오른쪽 끝 (j==i) → 이전 층의 바로 왼쪽 열
• 나머지 (0 < j < i) → 이전 층의 j-1, j 중 큰 값 선택

⸻

소스 코드 (Python)

import sys

input = sys.stdin.readline

n = int(input())
nums = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * n for _ in range(n)]

dp[0][0] = nums[0][0]

for i in range(1, n):
    for j in range(i + 1):
        if j == 0:
            dp[i][j] = dp[i - 1][j] + nums[i][j]
        elif j == i:
            dp[i][j] = dp[i - 1][j - 1] + nums[i][j]
        else:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + nums[i][j]

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


⸻

코드 설명
• 입력 처리: sys.stdin.readline()으로 빠르게 입력받고, nums 리스트에 삼각형을 저장합니다.
• dp 배열 초기화: n x n 크기의 2차원 리스트를 0으로 초기화합니다.
• 점화식:
• 가장 왼쪽: 위에서 내려오는 경로 하나 → dp[i][j] = dp[i-1][j] + nums[i][j]
• 가장 오른쪽: 대각선 왼쪽 경로 하나 → dp[i][j] = dp[i-1][j-1] + nums[i][j]
• 가운데: 두 경로 중 최대 선택 → max(dp[i-1][j-1], dp[i-1][j]) + nums[i][j]
• 결과 출력: 마지막 줄 dp[n-1] 중 가장 큰 값이 최대 경로 합입니다.

⸻