[python] 백준 2096 내려가기

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

2096번: 내려가기

 

문제 해결

사실 문제 자체는 매우 쉽다. (dp를 이용해서 0열, 1열, 2열에 각각 올 수 있는 이전 행 최고 누적합을 가져오서 더하면 되므로)

하지만 메모리가 4MB 밖에 안주어진다. 정확한 양은 체감을 못해도 평소 250~500MB 되는 문제도 많은 것을 보면 엄청 적다는 것을 알 수 있다.

따라서 리스트를 n행 모두 사용하는 것이 아니라(dp[0], dp[1], .... 사용하면 메모리가 커진다..) 한 행만 사용하고 한 줄씩 비교를 해가며 바로 수정해가야한다.

 

CODE

import sys
INF = sys.maxsize
n = int(input())
Mdp = [0]*3
mdp = [0]*3
Mtp = [0]*3
mtp = [0]*3
for _ in range(n):
    a, b, c = map(int, input().split())
    for j in range(3):
        if j==0:
            Mtp[0] = a + max(Mdp[0],Mdp[1])
            mtp[0] = a + min(mdp[0],mdp[1])
        elif j == 1:
            Mtp[1] = b + max(Mdp)
            mtp[1] = b + min(mdp)
        else:
            Mtp[2] = c + max(Mdp[1], Mdp[2])
            mtp[2] = c + min(mdp[1], mdp[2])
    for i in range(3):
        Mdp[i] = Mtp[i]
        mdp[i] = mtp[i]
print(max(Mdp), min(mdp), sep=' ')