백준 1932 정수 삼각형

https://www.acmicpc.net/problem/1932

 

 이 문제는 정수 삼각형이 주어지고 피라미드의 맨 위부터 오직 맞닿아 있는 아래 오른 대각선, 아래 왼 대각선으로 쭈욱 내려갔을 때, 그 경로에 있는 숫자의 합이 최대인 값을 구하는 문제이다.

 이 문제 또한 간단하게 다이나믹 프로그램으로 그 점에서 최댓값이 되게하는 값을 순간순간 저장해가며 전진해나가 끝의 값 중 가장 큰 값을 출력하면 된다.

 

import sys
input = sys.stdin.readline

def finding_max(pyramid):
    matrix = [[0]]+[[0]*n for n in range(1,N+1)]
    for i in range(1,N+1):
        for idx in range(len(matrix[i])):
            if idx == 0:
                matrix[i][idx] = matrix[i-1][idx] + pyramid[i][idx]
            elif idx == len(matrix[i])-1:
                matrix[i][idx] = matrix[i-1][idx-1] + pyramid[i][idx]
            else:
                matrix[i][idx] = max(matrix[i-1][idx-1],matrix[i-1][idx]) + pyramid[i][idx]

    return max(matrix[N])


N = int(input().rstrip())
pyramid = [[0]]

for _ in range(N):
    pyramid.append(list(map(int,input().rstrip().split())))

print(finding_max(pyramid))