백준) 정수삼각형 나의 사고과정

문제링크

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

1932번: 정수 삼각형

각 층의 요소마다 최대값을 계산하는방식으로 구현을 해보아야할것같다

다만 n은 최대 500까지 나오고 그렇게되면 한층당 계산해야할 요소개수가 500개로 늘어나기때문에 조금 걸리긴하지만

시간제한은 넉넉한 편인것같으니 한번 구현해보았다

 

원트에 성공하였다

RGB거리와 같은방식으로 풀었다

 

핵심은 도착지점마다 계속 최대값을 구하고 갱신시켜 나가는것이다 

이렇게 하면 이미 계산한 경로를 다시 되돌아가 풀지않아도 된다(동적계획법)

# 정수 삼각형
import sys
input=sys.stdin.readline

N=int(input()) # 층
d=[[int(input())]]
for i in range(N-1):
    d.append([]) # N개만큼의 층 구현
for i in range(1,N):
    a=list(map(int,input().split()))
    for j in range(len(a)):
        if j==0:
            d[i].append(a[j]+d[i-1][0])
        elif j!=0 and j!=len(a)-1:
            d[i].append(a[j]+max(d[i-1][j], d[i-1][j-1]))
        else:
            d[i].append(a[j]+d[i-1][-1])

print(max(d[-1]))