[DP] 1932 정수 삼각형

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

1932번: 정수 삼각형

# 2023.01.01
import sys
input = sys.stdin.readline

n = int(input())
triangle=[list(map(int, input().split())) for _ in range(n)]

for i in range(n-1, -1, -1):
    for j in range(i):
        triangle[i-1][j]+=max(triangle[i][j], triangle[i][j+1])

print(triangle[0][0])

위에서 아래로 내려가면서 값을 더하는 방법도 있지만

 

아래에서 위로 올라가면서 값을 저장하며 더하는 방법이 더 쉽다

triangle[i-1][j] +=max(triangle[i][j], triangle[i][j+1]) 이 핵심

현재 층 += 대각선 왼쪽 or 대각선 오른쪽 중 더 큰 값

 

결국 답은 삼각형의 제일 위에 있는 값을 출력해주면 된다