🟩 [백준] [Python] [Gold5] 2096번_내려가기

문제

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

2096번: 내려가기

풀이

# 백준 2096번 문제 - 내려가기
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
maxDP = arr
minDP = arr
for _ in range(n-1):
    arr = list(map(int, input().split()))
    maxDP = [arr[0] + max(maxDP[0], maxDP[1]), arr[1] + max(maxDP), arr[2] + max(maxDP[1], maxDP[2])]
    minDP = [arr[0] + min(minDP[0], minDP[1]), arr[1] + min(minDP), arr[2] + min(minDP[1], minDP[2])]

print(max(maxDP), min(minDP))

DP 문제이지만 기존의 메모제이션 방식을 그대로 사용하면 메모리 초과가 발생한다.

메모제이션을 할 때 사용하지 않는 값을 배열에 저장하지 않고 배열을 새롭게 갱신시켜줘야한다.

따라서 minDP와 maxDP를 나누어서 구한다. 

구하는 방식은 맨 첫줄은 DP에 저장하고

0번째 인덱스는 다음줄의 0, 1 인덱스 중 큰 값을 선택하고

1번째 인덱스는 다음줄 중에 가장 큰 값을 선택하면 되고 

2번째 인덱스는 다음줄의 1, 2 인덱스 중 큰 값을 선택한다.