백준 / 골드 5 / 2096 내려가기 / Python [DP]

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

메모리 초과

import sys
input = sys.stdin.readline

N = int(input())
M = [None] * N
m = [None] * N
for i in range(N):
    M[i] = list(map(int, input().split()))
    m[i] = M[i][:]

for i in range(1, N):
    M[i][0] = M[i][0] + max(M[i-1][0], M[i-1][1])
    M[i][1] = M[i][1] + max(M[i-1][0], M[i-1][1], M[i-1][2])
    M[i][2] = M[i][2] + max(M[i-1][1], M[i-1][2])
    
    m[i][0] = m[i][0] + min(m[i-1][0], m[i-1][1])
    m[i][1] = m[i][1] + min(m[i-1][0], m[i-1][1], m[i-1][2])
    m[i][2] = m[i][2] + min(m[i-1][1], m[i-1][2])

maxi = 0
mini = sys.maxsize
for i in range(3):
    maxi = max(maxi, M[N-1][i])
    mini = min(mini, m[N-1][i])
print(maxi, mini)

배열에 저장하지 않고 바로 처리로 해결

import sys
input = sys.stdin.readline

N = int(input())
Sl, Sc, Sr = 0, 0, 0
sl, sc, sr = 0, 0, 0

for i in range(N):
    l, c, r = map(int, input().split())
    
    Tl = l + max(Sl, Sc)
    Tc = c + max(Sl, Sc, Sr)
    Tr = r + max(Sc, Sr)
    Sl, Sc, Sr = Tl, Tc, Tr
    
    tl = l + min(sl, sc)
    tc = c + min(sl, sc, sr)
    tr = r + min(sc, sr)
    sl, sc, sr = tl, tc, tr
    
print(max(Sl,Sc,Sr), min(sl,sc,sr))