[백준 2096번] 내려가기

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

import sys

input = sys.stdin.readline

n = int(input())

dp_max = [0]*3
dp_min = [0]*3

for _ in range(n):

    a, b, c = map(int,input().split())

    temp_max = dp_max[:]
    temp_min = dp_min[:]

    for i in range(3):
        if i == 0:
            dp_max[i] = a + max(temp_max[0],temp_max[1])
            dp_min[i] = a + min(temp_min[0],temp_min[1])
        elif i == 1:
            dp_max[i] = b + max(temp_max[0],temp_max[1],temp_max[2])
            dp_min[i] = b + min(temp_min[0],temp_min[1],temp_min[2])
        elif i == 2:
            dp_max[i] = c + max(temp_max[1],temp_max[2])
            dp_min[i] = c + min(temp_min[1],temp_min[2])

print(max(dp_max),min(dp_min))

# 메모리 초과 코드
# scores = [list(map(int,input().split())) for _ in range(n)]

# dp = [[0]*3 for _ in range(n)]
# dp_2 = [[float("inf")]*3 for _ in range(n)]

# dp[0][0], dp[0][1], dp[0][2] = scores[0][0], scores[0][1], scores[0][2]
# dp_2[0][0], dp_2[0][1], dp_2[0][2] = scores[0][0], scores[0][1], scores[0][2]

# for i in range(1,n):
#     for j in range(3):
#         if j == 0:
#             dp[i][j] = max(dp[i-1][0], dp[i-1][1]) + scores[i][j]
#             dp_2[i][j] = min(dp_2[i-1][0], dp_2[i-1][1]) + scores[i][j]
#         elif j == 1:
#             dp[i][j] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2]) + scores[i][j]
#             dp_2[i][j] = min(dp_2[i-1][0], dp_2[i-1][1], dp_2[i-1][2]) + scores[i][j]
#         elif j == 2:
#             dp[i][j] = max(dp[i-1][1], dp[i-1][2]) + scores[i][j]
#             dp_2[i][j] = min(dp_2[i-1][1], dp_2[i-1][2]) + scores[i][j]

# print(f"{max(dp[-1])} {min(dp_2[-1])}")

 

이번 문제는 3개의 공간과 N개의 층으로 이루어진 공간에서 맨 위층에서 맨 아래층까지 이동하여 얻을 수 있는 최대값과 최소값을 구하는 문제이다.

 

큰 문제(마지막 층까지 도착했을 경우의 최대값/최소값)을 구하기 위해 작은 문제(i번째 층까지 이동했을 때의 최소값/최대값)을 활용할 수 있고, 중간 과정을 메모리에 저장함으로써 중복되는 연산을 줄일 수 있는 문제이기 때문에 DP 알고리즘을 사용하였다.

 

그런데, 처음에 최대값을 구하기 위한 dp 테이블과 최소값을 구하기 위한 dp 테이블을 선언하고 제출하고나니 메모리 초과가 발생하였다.(아무래도 dp의 크기가 최대 10^5 x 3 인데, 이를 2개 선언을 해서 그런지 메모리가 초과되는 것 같다.)

 

여기서 슬라이딩 윈도우를 사용할 수 있는데, dp 테이블을 Nx3크기로 만드는 것이 아니라 1x3 크기로 만들어서 테이블을 재활용하는 것이 핵심이다.

 

이것이 가능한 이유는 DP 점화식은 항상 바로 이전(윗 층)의 값을 바탕으로 판단하기 때문에 굳이 Nx3 크기로 테이블을 선언하지 않고, 1x3 크기로 만들어서 바로바로 재활용하여 메모리를 아낄 수 있기 때문이다.