[다이나믹 프로그래밍] 백준 2096번: 내려가기 / 골드 4

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

2096번: 내려가기

import sys
n = int(sys.stdin.readline())

max_dp = list(map(int, sys.stdin.readline().split()))
min_dp = max_dp

for i in range(1, n):
    a, b, c = map(int, sys.stdin.readline().split())

    na1 = a + max(max_dp[0], max_dp[1])
    nb1 = b + max(max_dp[0], max_dp[1], max_dp[2])
    nc1 = c + max(max_dp[1], max_dp[2])
    max_dp = [na1, nb1, nc1]

    na2 = a + min(min_dp[0], min_dp[1])
    nb2 = b + min(min_dp[0], min_dp[1], min_dp[2])
    nc2 = c + min(min_dp[1], min_dp[2])
    min_dp = [na2, nb2, nc2]

print(max(max_dp), min(min_dp))

dp로 풀 수 있는 문제다.

앞에서부터 모든 경우를 조사해나가면 경우의수가 기하급수적으로 커지기 때문에

현 단계를 기준으로 이전 단계의 행 중 적절한 값을 취하는 형태로 나아가야 한다.