[백준] 1932번: 정수 삼각형 (다이나믹 프로그래밍)

 

이 문제 역시 다이나믹 프로그래밍으로 접근해야하는 문제이다.

 

본인은 bottom-up 방식으로 문제를 해결하였다.

 

어떤 층을 기준으로 왼쪽 아래 삼각형에서의 합이 최대가 되는 경로의 수의 합과 오른쪽 아래 삼각형에서의 합이 최대가 되는 경로의 수의 합을 비교해서 더 큰 값을 채택하는 방식으로 차근차근 올라간다.

 

메모제이션 기법으로 triangle 리스트에 답을 갱신하고 원하는 값을 구해낸다.

 

 

문제 풀이

import sys
input = sys.stdin.readline
n = int(input())
triangle = [list(map(int, input().split())) for _ in range(n)]
triangle.sort(key=lambda x: len(x), reverse=True)
for i in range(1, n):
    for j in range(n-i):
        triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j+1])
print(triangle[-1][0])