알고리즘 스터디

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

히치키치 2021. 7. 6. 13:07

문제

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

 

2096번: 내려가기

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

www.acmicpc.net

 

요점

  • 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))