1932-백준-정수 삼각형

1. 문제 출처

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

1932번: 정수 삼각형

2. 풀이

모든 위치에서의 최대값을 구한다..

이를 매번 처음부터 구하면 매우 오래 걸리므로 Dynamic Programming (동적 프로그래밍)을 사용한다..아래는 Botton_Top 형식으로 구현하였다.

# 입력
n = int(input())
# 정수 삼각형 입력
tri = [[0]*idx for idx in range(1,n+1)]

for idx in range(n):
    tri[idx] = list(map(int,input().split()))

# dp 다이나믹 프로그래밍으로 중복되는 계산과정 없이 한번에 계산(Botton_Top)
def solution():
    for level in range(1,n):
        for idx in range(len(tri[level])):
            right = -1 if (idx == len(tri[level])-1) else (tri[level][idx] + tri[level-1][idx])
            left = -1 if (idx == 0) else  (tri[level][idx] + tri[level-1][idx-1])
            left_idx = idx -1
            tri[level][idx] = max(left,right)
    print(max(tri[n-1]))
            
    
solution()