1932 정수 삼각형

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

✔ 유형 : DP

✔ 문제 풀이: DP memorization 방식으로 2차원 배열에 작은 값의 결과부터 저장

 

 

문제 접근

 

 

DP 점화식

 

 

코드

import sys
input = sys.stdin.readline

# input 1
N = int(input()) # size of triangle

arr = list()
DP = [[0 for _ in range(N)] for _ in range(N)] # memorization

# input 2
for i in range(N):
    line = list(map(int, input().split()))
    
    arr.append(line)

# initial value
DP[0][0] = arr[0][0]

# level of the triangle
level = 0

# bottom-up
while(level < N-1):
    for i in range(0,len(arr[level])): # list of the level line
        DP[level+1][i] = max(DP[level+1][i], DP[level][i] + arr[level+1][i]) 
        DP[level+1][i+1] = max(DP[level+1][i+1], DP[level][i] + arr[level+1][i+1])
        
    
    level += 1
    
print(max(DP[level])) # 해당 라인에서 가장 큰 값 프린트