[CLASS 4]백준 2096번 - 내려가기

2096번 : 내려가기

 

이전에 비슷한 DP문제를 풀어본적이 있어서 드물게 빠르게 풀 수 있는 문제였다. 풀고나서 알았는데 이런 문제를 슬라이딩 윈도우 라고 부르나보다.

 

다만 주의할 점은 메모리 제한이 4MB로 정해져 있기 때문에 100만 길이의 리스트를 만들면 십중팔구 메모리 초과에 걸릴 것이다.

 

따라서 그냥 한줄씩 입력받으면서 DP를 수행하면 된다.

 

내 코드:

# dawitblog.tistory.com/154
from sys import stdin
input = stdin.readline

n = int(input())
a,b,c = map(int,input().split())
current_max = [a,b,c]
current_min = [a,b,c]
for _ in range(n-1):
    a,b,c = map(int,input().split())
    temp = tuple(current_max)
    current_max[0] = max(temp[0],temp[1]) + a
    current_max[1] = max(temp) + b
    current_max[2] = max(temp[1],temp[2]) + c

    temp = tuple(current_min)
    current_min[0] = min(temp[0],temp[1]) + a
    current_min[1] = min(temp) + b
    current_min[2] = min(temp[1],temp[2]) + c

print(max(current_max),min(current_min))

 

이게 왜 골드 4??