[백준] 2096번 : 내려가기 - Python(파이썬)

문제

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

2096번: 내려가기

 

요점

• dp 배열
• 슬라이딩 윈도우
• 까다로운 메모리

 

점화식 원리

 

코드

#문제 : https://www.acmicpc.net/problem/2096

n=int(input())
table=[list(map(int,input().split()))for _ in range(n)]
large=small=table[0]


for i in range(1,n):
    large=[max(large[0],large[1])+table[i][0],
        max(large[0],large[1],large[2])+table[i][1],
        max(large[1],large[2])+table[i][2]]
    small=[min(large[0],large[1])+table[i][0],
        min(large[0],large[1],large[2])+table[i][1],
        min(large[1],large[2])+table[i][2]]

print(max(large),min(small))