[동적계획법/DP] 백준 1932 정수 삼각형 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1932번: 정수 삼각형

 

 

 

2. 문제 풀이

정수 삼각형

 위와 같은 정수삼각형이 입력으로 주어집니다. 맨 위층부터 아래층까지 수를 합하며, 위와 같이 맞닿은 아랫층 숫자만 더할 수 있습니다. (대각선 왼쪽 혹은 오른쪽에 있는 수)

 

 위 예제에서는 7 + 3 + 8 + 7+ 5 = 30이 가장 큰 수입니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 맨 위층부터 아래층까지 차곡차곡 더해나가는 방식이므로, DP를 이용합니다. 

 

cost[i][j] += max(cost[i-1][j-1], cost[i-1][j])

 이전 층의 왼쪽 혹은 오른쪽 중 큰 걸로 선택해서 더하면, 맨 아랫층에서 가장 합이 큰 수를 찾을 수 있습니다.

 주의할 점은 삼각형의 변에 위치한 수의 경우, 비교할 대상이 없습니다. 따라서 이 경우만 예외처리 해주시면 됩니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

#입력
N = int(input())
cost = []
for _ in range(N):
    cost.append([-1]+list(map(int, input().split()))+[-1])

#DP
for i in range(1, N):
    for j in range(1, i+2):
        cost[i][j] += max(cost[i-1][j-1], cost[i-1][j])

print(max(cost[N-1]))

실행결과

 저는 -1로 양 옆 테두리를 만들어서 DP를 작성했습니다. 입력범위가 0 ~ 9999이므로, -1은 자연스럽게 무시하게 됩니다. 또는 j == 0일때와 j == i일 때만 따로 처리해주셔도 됩니다.

 알고리즘의 대원칙에 따라, -1을 추가할 메모리를 더 쓰면 조건분기를 줄일 수 있으므로 실행시간이 단축되며, 조건분기를 나눠서 처리하면 메모리를 덜 쓰지만 조금 더 오래 걸리게 됩니다.