BOJ2096 내려가기

문제

BOJ2096 내려가기
골드IV | 백준 2096 | Python3 파이썬 풀이

알고리즘

쉬운 DP 문제이나, 메모리 제한이 4MB로 매우 작다.
즉, 슬라이딩 윈도우 기법을 사용해야 한다. 슬라이딩 윈도우는 원래 네트워크에서 버퍼를 구성하는 방식인데, 알고리즘에서는 메모리 사용량을 줄이기 위해 사용한다.

위 그림에서 왼쪽처럼 DP 배열을 구성하는 것이 일반적이다. (대부분 문제에서는 메모리를 넉넉하게 주기 때문)
메모리 제한이 작은 문제는 메모리를 아끼기 위해서 필요 없는 부분은 버려야 한다. 오른쪽 그림처럼 DP 배열의 일부만 구현하면서 전체적인 그림에서는 부분 배열이 계속 내려가는 모양이 된다.
이 문제에서는 현재 DP행을 구하기 위해 오직 이전의 DP행의 정보만 필요하므로 이전 DP행 위쪽(이전) 정보는 버린다. 즉 두 행을 스위치하며 슬라이딩 윈도우를 구현한다.

코드

import sys

input = sys.stdin.readline

N = int(input())

MaxDP = [[0, 0, 0], [0, 0, 0]]
MinDP = [[0, 0, 0], [0, 0, 0]]

scores = list(map(int, input().split()))

MaxDP[0][0] = scores[0]
MaxDP[0][1] = scores[1]
MaxDP[0][2] = scores[2]
MinDP[0][0] = scores[0]
MinDP[0][1] = scores[1]
MinDP[0][2] = scores[2]

for _n in range(1, N):
    scores = list(map(int, input().split()))
	
    # DP값 계산
    MaxDP[1][0] = scores[0] + max(MaxDP[0][0], MaxDP[0][1])
    MaxDP[1][1] = scores[1] + max(MaxDP[0])
    MaxDP[1][2] = scores[2] + max(MaxDP[0][1], MaxDP[0][2])

    MinDP[1][0] = scores[0] + min(MinDP[0][0], MinDP[0][1])
    MinDP[1][1] = scores[1] + min(MinDP[0])
    MinDP[1][2] = scores[2] + min(MinDP[0][1], MinDP[0][2])
	
    # 행 교체 (슬라이딩 윈도우) 필요없는 정보는 버림
    MaxDP[0][0] = MaxDP[1][0]
    MaxDP[0][1] = MaxDP[1][1]
    MaxDP[0][2] = MaxDP[1][2]
    MinDP[0][0] = MinDP[1][0]
    MinDP[0][1] = MinDP[1][1]
    MinDP[0][2] = MinDP[1][2]

print(max(MaxDP[0]), min(MinDP[0]))

결과

슬라이딩 윈도우를 사용하지 않으면 메모리 초과가 발생한다.