[백준] 2096 - 내려가기

문제 설명

문제 링크

문제 풀이

해당 문제는 DP문제임으로 아래와 같은 점화식을 세울 수 있다. 예전에 보았던, 연속으로 포도주를 마시것은 최대 두 번만 가능한 문제와 비슷한 느낌이다.

max_table1[i] = arr[i][0] + max(max_table1[i-1], max_table2[i-1])
max_table2[i] = arr[i][1] + max(max_table1[i-1], max_table2[i-1], max_table3[i-1])
max_table3[i] = arr[i][2] + max(max_table2[i-1], max_table3[i-1])

이렇게 해서 구현한 코드는 다음과 같았다:

import stdin
input = sys.stdin.readline

N = int(input())

arr = list(map(int, input().split()))
max_table = arr
min_table = arr

코드

import stdin
input = sys.stdin.readline

N = int(input())

arr = list(map(int, input().split()))
max_table = arr
min_table = arr
for _ in range(N - 1):
    arr = list(map(int, input().split()))

    max_table = [arr[0] + max(max_table[0], max_table[1]), arr[1] + max(max_table), arr[2] + max(max_table[1], max_table[2])]
    min_table = [arr[0] + min(min_table[0], min_table[1]), arr[1] + min(min_table), arr[2] + min(min_table[1], min_table[2])]

print(max(max_table), min(min_table))