[2096] 내려가기

처음에 2차원 리스트로 만들었더니 메모리 초과 ㅠㅠ

어쩐지 너무 쉽더라

import sys
import heapq

input = sys.stdin.readline

n = int(input())
gra = []
gra.append([0 for _ in range(n + 2)])

for i in range(1, n + 1):
    li = list(map(int, input().strip().split()))
    gra.append([0] + li + [0])

xdp = [[0] * (n + 2) for _ in range(n + 1)]
ndp = [[sys.maxsize] * (n + 2) for _ in range(n + 1)]
ndp[0] = [0 for _ in range(n + 2)]

for i in range(1, len(gra)):
    for j in range(1, n + 1):
        xdp[i][j] = gra[i][j] + max(xdp[i - 1][j - 1], xdp[i - 1][j], xdp[i - 1][j + 1])
        ndp[i][j] = gra[i][j] + min(ndp[i - 1][j - 1], ndp[i - 1][j], ndp[i - 1][j + 1])


print(max(xdp[n]), min(ndp[n]))

 

1차원 배열로 해야 한다

입력 받으면서 바로 바로 값을 변경 해야한다

import sys
import heapq

input = sys.stdin.readline

n = int(input())
pre = list(map(int, input().strip().split()))
xdp = pre[:]
ndp = pre[:]

for _ in range(1, n):
    gra = list(map(int, input().strip().split()))
    # 왼쪽 일 때
    x1 = gra[0] + max(xdp[0], xdp[1])
    n1 = gra[0] + min(ndp[0], ndp[1])
    # 가운데 일 때
    x2 = gra[1] + max(xdp[0], xdp[1], xdp[2])
    n2 = gra[1] + min(ndp[0], ndp[1], ndp[2])
    # 오른쪽 일 때
    x3 = gra[2] + max(xdp[1], xdp[2])
    n3 = gra[2] + min(ndp[1], ndp[2])
    xdp = [x1, x2, x3]
    ndp = [n1, n2, n3]

print(max(xdp), min(ndp))