[Python] 백준 / gold / 2096번 (내려가기)

문제 링크 : https://www.acmicpc.net/problem/2096

극한의 메모리 관리가 뭔지 알게 해준 문제..
이 문제는 메모리 제한이 4MB이다.
int 자료형은 4Byte 인 것을 알고 있기 때문에, 얼추 (10^6) 이하 정도 개수의 메모리를 사용해야 되겠다고 생각했다.

그런데 이 문제의 input 조건은 (1<=N<=100,000)이기 때문에 매우 촉박하다.
문제의 input 조건을 차례로 메모리에 담기만 해도 메모리 제한이 간당간당 해진다.

처음 풀 땐 시간복잡도만 고려하고, Dynamic Programming 으로 푼 뒤에 맞았겠지,, 했는데 공간복잡도 까지 고려해야 했었다.

메모리 실패 코드

import sys
N = int(sys.stdin.readline())
graph = []
for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))

minDP = [[0]*3 for _ in range(N)]
maxDP = [[0]*3 for _ in range(N)]

minDP[0] = [graph[0][0], graph[0][1], graph[0][2]]
maxDP[0] = [graph[0][0], graph[0][1], graph[0][2]]

for i in range(1, N):
    a, b, c = graph[i][0], graph[i][1], graph[i][2]

    minDP[i][0] = min(minDP[i-1][0]+a, minDP[i-1][1]+a)
    minDP[i][1] = min(minDP[i-1][0]+b, minDP[i-1][1]+b, minDP[i-1][2]+c)
    minDP[i][2] = min(minDP[i-1][1]+b, minDP[i-1][2]+c)

    maxDP[i][0] = max(maxDP[i - 1][0] + a, maxDP[i - 1][1] + a)
    maxDP[i][1] = max(maxDP[i - 1][0] + b, maxDP[i - 1][1] + b, maxDP[i - 1][2] + b)
    maxDP[i][2] = max(maxDP[i - 1][1] + b, maxDP[i - 1][2] + c)

print(max(maxDP[N-1]), min(minDP[N-1]))

정답 코드

import sys
N = int(sys.stdin.readline())

for _ in range(1):
    a, b, c = map(int, sys.stdin.readline().split())

minDP = [[0]*3 for _ in range(2)]
maxDP = [[0]*3 for _ in range(2)]

minDP[0] = [a, b, c]
maxDP[0] = [a, b, c]

if N == 1: 
    print(max(maxDP[0]), min(minDP[0]))
    exit(0)

for _ in range(1, N):
    a, b, c = map(int, sys.stdin.readline().split())

    minDP[1][0] = min(minDP[0][0], minDP[0][1]) + a
    minDP[1][1] = min(minDP[0][0], minDP[0][1], minDP[0][2]) + b
    minDP[1][2] = min(minDP[0][1], minDP[0][2]) + c

    maxDP[1][0] = max(maxDP[0][0], maxDP[0][1]) + a
    maxDP[1][1] = max(maxDP[0][0], maxDP[0][1], maxDP[0][2]) + b
    maxDP[1][2] = max(maxDP[0][1], maxDP[0][2]) + c

    minDP[0] = minDP[1][:]
    maxDP[0] = maxDP[1][:]

print(max(maxDP[1]), min(minDP[1]))

1. DP table을 N 크기로 설정할 필요가 없었다.
   바로 전, 그리고 현재 table만 저장할 수 있으면 된다.
   그래서 이 문제는 크기 2의 window를 갖는 슬라이딩 윈도우 문제로도 분류될 수 있다.

2. 입력을 받아들이는 순간 graph에 저장하는 것이 아니고, DP table에 삽입해버린다.

3. 그리고 N=1 인 경우 히든 케이스를 고려해준다.
   
   

프로그래머스에서 땅따먹기라는 문제가 있는데, 그 문제와 진짜 비슷하다. 근데 그 문제는 DP table을 N 전체 크기로 잡아도 정답처리 됐던걸로 기억한다.

땅따먹기 : https://programmers.co.kr/learn/courses/30/lessons/12913

땅따먹기 정답 코드

def solution(land):
    answer = 0
    dp = [[0]*4 for _ in range(len(land))]
    dp[0] = land[0]
    
    for i in range(1,len(land)):
        for x in range(4):
            dp[i][x] = max(dp[i-1][:x]+dp[i-1][x+1:]) + land[i][x]
    
    return max(dp[-1])