내려가기

알고리즘 구분 : 다이나믹 프로그래밍, 슬라이딩 윈도우

문제 풀이 : 문제의 내용에서 다음 줄로 내려갈 때의 제약 조건이 명확하게 정해져 있으며, 해당 조건 내에서 최대 점수와 최소 점수를 찾으라는 내용을 통해서 점화식을 통해 구현하는 다이나믹 프로그래밍 문제로 생각하고 진행하면 된다. 여기서 가장 조심해야할 부분은 문제의 기본 조건이다. 메모리 제한이 4MB이다. 즉, 단순히 다이나믹 프로그래밍을 구현하는 것이 아닌, 메모리를 최소화하는 방식으로 문제를 풀어야 한다는 것이다.
만약 메모리 제한이 여유로웠다면, 각 줄별 점수 입력을 2차원 리스트로 받은 이후, 동일한 크기의 dp리스트를 최대 dp리스트와 최소 dp리스트를 만들어서 각각 만든 점화식을 반복문 내에서 돌리면 맞출 수 있었을 것이다.
메모리를 최소화하기 위해선, 리스트의 메모리를 최소한 줄이는 것이 핵심이므로, 입력받을 때마다 바로바로 dp리스트를 채울 수 있도록 하였다. 그 다음, 각 최대, 최소 dp리스트는 2*3크기의 리스트에서 dp[0]은 이전 줄까지 계산한 값, dp[1]은 이전 줄의 max or min 값 + 현재 줄의 값의 합을 저장할 수 있도록 구현했고, 이후 dp[0] = dp[1]을 통해서 새로운 계산을 위해 지금까지 계산된 값을 이전 값의 위치로 옮길 수 있도록 했다.

소스 코드 :

import sys

n = int(sys.stdin.readline())

dp = [[0] * 3 for _ in range(2)]
dpMin = [[0] * 3 for _ in range(2)]
for i in range(n):
    line = list(map(int, sys.stdin.readline().split()))

    dp[1][0] = line[0] + max(dp[0][0], dp[0][1])
    dp[1][1] = line[1] + max(dp[0][0], dp[0][1], dp[0][2])
    dp[1][2] = line[2] + max(dp[0][1], dp[0][2])

    dpMin[1][0] = line[0] + min(dpMin[0][0], dpMin[0][1])
    dpMin[1][1] = line[1] + min(dpMin[0][0], dpMin[0][1], dpMin[0][2])
    dpMin[1][2] = line[2] + min(dpMin[0][1], dpMin[0][2])

    dp[0][0], dp[0][1], dp[0][2] = dp[1][0], dp[1][1], dp[1][2]
    dpMin[0][0], dpMin[0][1], dpMin[0][2] = dpMin[1][0], dpMin[1][1], dpMin[1][2]

print(max(dp[1]), min(dpMin[1]))

주의할 점
deepcopy 모듈을 사용해서 깊은 복사하려고 했었으나
이 것이 오히려 메모리 초과에 영향을 미치고 있었다.
최소한의 메모리를 사용하여야 할 때에는 deepcopy를
배제하고 문제를 풀어야 할 것 같다.

• 문제 출처 : https://www.acmicpc.net/problem/2096
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.