백준 2096 내려가기

 

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

 

 이 문제는 주어진 매트릭스의 맨 위에서 아래로 내려가며 더했을 때 가장 큰 값과 가장 작은 값을 구하는 문제이다. 이 때 내려갈때는 바로 아래로 내려가거나 바로 아래와 붙어있는 칸으로만 내려갈 수 있단 점이다.

 

 이 문제는 그동안 풀어온 다이나믹 프로그래밍처럼 풀면

 max_matrix[i][0] = max(max_matrix[i-1][:2]) + graph[i][0]
max_matrix[i][1] = max(max_matrix[i-1]) + graph[i][1]
max_matrix[i][2] = max(max_matrix[i-1][1:]) + graph[i][2]

 

 와 같은 점화식으로 구할 수 있을 것만 같다.

 

 하지만 이 문제는 그동안 메모리를 어느정도 희생하면서 메모이제이션을 하면서 시간복잡도를 줄인 다이나믹 프로그래밍 문제들과 달리 메모리 제한이 4MB란 빡빡한 제한을 갖고 있다.

 

 그렇기에 우리는 메모이제이션을 할 때 당장 필요한 것만 저장하며 나머지는 저장하지 않는 그런 느낌으로 풀어야한다. 일종의 슬라이딩 윈도우 알고리즘으로, 위에서 아래로 훑으며 내려오며 그 윈도우만을 저장한다는 감각으로 풀면 메모리를 상당수 아낄 수 있다.

 

import sys
input = sys.stdin.readline

N=int(input().rstrip())
graph=[]
arr= list(map(int,input().rstrip().split()))
max_DP = arr
min_DP = arr

for _ in range(N-1):
    now=list(map(int,input().rstrip().split()))
    max_DP = [now[0]+max(max_DP[:2]),now[1]+max(max_DP),now[2]+max(max_DP[1:])]
    min_DP = [now[0]+min(min_DP[:2]),now[1]+min(min_DP),now[2]+min(min_DP[1:])]

print(max(max_DP),min(min_DP))