[BOJ] 내려가기

코드

import sys
import copy
input = sys.stdin.readline

n = int(input())

# 한 줄씩 읽고 계산하고 버려야 메모리 초과를 피할 수 있다
maxPrev = [0,0,0]
minPrev = [0,0,0]

for _ in range(n):
    inp = list(map(int, input().split()))
    tmp = [0,0,0]
    tmp[0] = inp[0] + max(maxPrev[:2])
    tmp[1] = inp[1] + max(maxPrev)
    tmp[2] = inp[2] + max(maxPrev[1:])
    maxPrev = copy.deepcopy(tmp)

    tmp[0] = inp[0] + min(minPrev[:2])
    tmp[1] = inp[1] + min(minPrev)
    tmp[2] = inp[2] + min(minPrev[1:])
    minPrev = copy.deepcopy(tmp)

print(max(maxPrev), min(minPrev))

결과

풀이 방법

• DP를 활용하여 해결하였다.
• 왼쪽, 중간, 오른쪽 위치마다 이전 줄에서 택할 수 있는 값들 중 최대/최소값을 더해가며 마지막 줄까지 계산한다.
• 다만 이 문제는 메모리 제한이 4MB이기 때문에 처음부터 전체 리스트를 저장하여 사용하면 메모리 초과가 발생하므로 한 줄씩 읽고 계산해야 했다.