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

 

1932번: 정수 삼각형

 

문제

 

 

위 그림은 크기가 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

 

풀이

 

전 문제와 마찬가지로 DFS가 아닌 최적 부분구조를 통해 푸는 문제이다.

 

삼각형의 정상부터 시작하여 내려가되 인접한 노드 중 큰 것을 더하여 내려주면 된다.

 

글보단 그림을 통해 알아보자.

 

위의 노드를 밑으로 더하되, 큰 것을 더해준다.

 

 

최종 숫자 배열이 구해졌다. 여기서 가장 큰 30을 출력하면 문제 해결.

 

이제 코드로 작성해보자.

 

import sys
n = int(sys.stdin.readline())
t = [list(map(int,sys.stdin.readline().split())) for i in range(n)]

for i in range(1,n):
    for j in range(len(t[i])):
        temp = []
        if j-1 != -1:
            temp.append(t[i-1][j-1])
            # -1은 null이 아니라 순서를 바꿔 뒤에서부터 출력이기 때문에
            # 조건을 추가해줬다.
        try:
            temp.append(t[i-1][j])
            # 맨 오른쪽 숫자의 경우 인덱스 초과 문제가 발생한다.
            # try except 문을 통해 오류를 무시하고 그냥 넘겨준다.
        except:
            pass
        t[i][j] += max(temp)
print(max(t[n-1]))