백준 1932번 - 정수 삼각형

정수 삼각형 문제 바로 가기

풀이 날짜: 2026-01-10

baekjoon 알고리즘 문제 풀이

풀이 코드

import sys
input = sys.stdin.readline

n = int(input())
dp = []
for _ in range(n):
    dp.append(list(map(int, input().split())))

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

        if j==i:
            up = 0
        else:
            up = dp[i-1][j]

        dp[i][j] = dp[i][j] + max(up, left_up)

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

내가 선택한 풀이 방식

문제의 핵심은, “각 위치까지 도달했을 때의 최대 누적 합을 어떻게 저장할 것인가”이다.

DP 배열

이 문제에서는 입력 배열 자체를 DP 배열로 사용했다.

• dp[i][j]: “i번째 줄의 j번째 위치까지 내려왔을 때 만들 수 있는 최대 합” 즉, dp[0][0]은 맨 위 숫자 하나만 선택했을 때의 합이며, dp[3][1]은 4번째 줄의 두 번째 숫자까지 내려왔을 때의 최대 합을 의미한다.

헷갈렸던 점

이중 for문 구조가 순간적으로 헷갈렸었다.
i는 줄 번호를 의미하므로,

• 0번째 줄 → 숫자 1개
• 1번째 줄 → 숫자 2개
• 2번째 줄 → 숫자 3개

즉, i번째 줄에는 항상 i+1개의 숫자가 있다.
따라서 j는 range(i+1)까지 돌아야 한다.