[파이썬/Python] 백준 1932(🥈1): 정수 삼각형

숨·2025년 8월 19일

코테

알고리즘 문제 풀이

목록 보기

115/128

📌 문제 : 백준 1932

📌 문제 탐색하기

n : 삼각형의 크기 ( $1 ≤ n ≤ 500$ )
integer : 삼각형 이루는 각 정수 ( $0 ≤ integer ≤ 9999$ )

문제 풀이

맨 위층부터 맨 아래층에 도달할 때까지 선택된 수의 합이 최대가 되는 경로를 구하는 문제이다.

각 층을 거쳐 얻은 선택된 수의 합은 이전 층에서 얻은 최댓값에서 현재 층의 최댓값을 더함으로써 얻을 수 있다.
→ 이전에 풀었던 문제 땅따먹기와 유사하게 DP로 해결할 수 있다.

예제 입력1을 예로 들었을 때 배열이 다음과 같다.
|7|
|3|8|
|8|1|0|
|2|7|4|4|
|4|5|2|6|5|

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 오른쪽에 있는 것만 선택 가능하므로
4층의 8은 7만, 3층의 1은 3 또는 8, 2층의 7은 8 또는 1을 선택할 수 있다.
→ 아래 있는 수는 자신의 왼쪽 위나 바로 위의 숫자 중 더 큰 수를 고를 수 있다.

즉, dp[i][j] += max(dp[i-1][j-1], dp[i-1][j])가 된다.

하지만 정수 삼각형이므로 배열의 범위가 벗어나지 않는지 확인하는 부분이 필요하다.

j=0이면 += dp[i-1][j]
j=len(triangle[i])이면(맨 끝이면) += dp[i-1][j-1]
그 외의 경우 += max(dp[i-1][j-1], dp[i-1][j])

조건에 따라 점화식을 반복하여 dp 테이블을 채운다면 마지막 칸에서 원하는 최댓값을 구할 수 있다.

가능한 시간복잡도

입력 → $O(N*N) = O(N^2)$
DP로 테이블 채우기 → $O(N*N) = O(N^2)$

최종 시간복잡도
최악일 때 $O(N^2) = O(250000)$ 이 되는데 이는 제한시간 2초 내 충분히 수행 가능하다.

알고리즘 선택

DP 활용

📌 코드 설계하기

입력
DP 계산
출력

📌 시도 회차 수정 사항

1회차

정수 삼각형이라는 특성을 고려하지 않고 일반 DP 테이블처럼 풀이해서 IndexError가 발생했다.
자신과 똑같은 열의 값이 없을 수도 있기 때문에 이를 고려해줘야 했다.

2회차

위의 방법으로 해결한 줄 알았는데 동일한 에러가 발생했다.
맨 오른쪽 값일 경우라는 조건을 작성할 때 j == len(triangle[i])라고 했는데 인덱스는 -1해주어야 하는 것을 잊었다.

3회차

잘못된 값이 출력되었다.
마지막 값으로 DP테이블의 맨 마지막 값을 내보내면 최댓값을 출력할 수 있겠다라고 생각했는데 다시 고민해보니 마지막 층 중에서도 최댓값을 출력해야 마지막까지 도달해서 얻은 정수 합 중 최대를 구할 수 있었다.

📌 정답 코드

import sys

input = sys.stdin.readline

# 입력
n = int(input())
triangle = [list(map(int, input().split())) for _ in range(n)]

# DP 계산
for i in range(1, n):
    for j in range(len(triangle[i])):
        # 맨 왼쪽일 경우 바로 위만 받음
        if j == 0:
            triangle[i][j] += triangle[i-1][j]
        # 맨 오른쪽일 경우 왼쪽 위만 받음
        elif j == len(triangle[i]) - 1:
            triangle[i][j] += triangle[i-1][j-1]
        # 그외엔 바로 위, 왼쪽 위 둘다 받음
        else:
            triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])

# 출력
print(max(triangle[-1]))