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

DP 개념 바로가기

문제

정수 삼각형 문제 링크

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

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

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

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

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

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

30

접근 방식

층을 내려가면서 부모의 최댓값을 선택하여 자신과 더한다

1) 층의 맨 처음과 마지막은 부모가 한개이므로 부모와 자신을 더한다

2) 층의 가운데는 부모가 둘 이므로 둘 중 큰 값을 자신과 더한다

3) 가장 마지막 층의 최댓값을 출력한다

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


         7
      10  15
    18  16  15
  20  25  20  19
24  30  27  26  24

코드

# url : https://www.acmicpc.net/problem/1932
# 난이도 : silver 1

import sys
n = int(input())


pre_layer = [int(input())]

for layer in range(2,n+1):
    cur_layer = list(map(int,sys.stdin.readline().split()))
    for i in range(len(cur_layer)):
        if i == 0 :
            cur_layer[0] += pre_layer[0]
        elif i == len(cur_layer) - 1:
            cur_layer[-1] += pre_layer[-1]
        else:
            cur_layer[i] += max(pre_layer[i-1], pre_layer[i])
    
    pre_layer = cur_layer

print(max(pre_layer))