백준 2096 내려가기 (파이썬)

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

첫번째 제출 코드 (메모리 초과)

import sys
def solve():
    MAX = 0
    MIN = 0
    for i in range(1, N):
        for j in range(3):
            if j == 0:
                dp[i][0] = arr[i][0] + max(dp[i-1][j], dp[i-1][j+1])
            elif j == 1:
                dp[i][1] = arr[i][1] + max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])
            else:
                dp[i][2] = arr[i][2] + max(dp[i - 1][j], dp[i - 1][j - 1])
    MAX = max(dp[-1])

    for i in range(1, N):
        for j in range(3):
            if j == 0:
                dp[i][0] = arr[i][0] + min(dp[i-1][j], dp[i-1][j+1])
            elif j == 1:
                dp[i][1] = arr[i][1] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])
            else:
                dp[i][2] = arr[i][2] + min(dp[i - 1][j], dp[i - 1][j - 1])
    MIN = min(dp[-1])
    print(MAX, MIN)
    return

if __name__=="__main__":
    input = sys.stdin.readline
    N = int(input())
    arr = []
    for i in range(N):
        arr.append(list(map(int, input().split())))
    dp = [i[:] for i in arr]
    solve()

 

메모리가 4MB인데 DP 값과 입력값을 한번에 저장시켜놓음

내려가면 이전 줄은 더 이상 연산을 하지 않아 필요가 없는 값들

논리는 맞으나 메모리 초과가 발생

  

두번째 제출(정답)

import sys
if __name__ == "__main__":
    input = sys.stdin.readline
    N = int(input())
    arr = []
    MAXtemp = [0, 0, 0]
    MINtemp = [0, 0, 0]
    MAXdp = [0, 0, 0]
    MINdp = [0, 0, 0]
    for i in range(N):
        arr = (list(map(int, input().split())))

        for j in range(3):
            if j == 0:
                MAXdp[0] = arr[0] + max(MAXtemp[j], MAXtemp[j + 1])
            elif j == 1:
                MAXdp[1] = arr[1] + max(MAXtemp[j - 1], MAXtemp[j], MAXtemp[j + 1])
            else:
                MAXdp[2] = arr[2] + max(MAXtemp[j], MAXtemp[j - 1])
        MAXtemp = MAXdp[:]

        for j in range(3):
            if j == 0:
                MINdp[0] = arr[0] + min(MINtemp[j], MINtemp[j + 1])
            elif j == 1:
                MINdp[1] = arr[1] + min(MINtemp[j - 1], MINtemp[j], MINtemp[j + 1])
            else:
                MINdp[2] = arr[2] + min(MINtemp[j], MINtemp[j - 1])
        MINtemp = MINdp[:]

    MIN = min(MINdp)
    MAX = max(MAXdp)
    print(MAX, MIN)

dp와 arr을 한번에 받아서 저장해두지 않고 한 번의 입력으로 MAXdp와 MINdp로 답을 가지고 있음

이전 dp 값에 영향이 가지 않게 하기 위해 temp를 따로 두어 매 줄 마다 최대 최소를 저장