백준 2096번 내려가기 골드5 - Python 풀이

다이나믹 프로그래밍을 활용하는 문제이다.

 

메모리 제한에 대한 생각 없이 단순히 메모이제이션에 대한 아이디어만 가지고 문제를 풀면 다음과 같은 풀이를 생각할 수 있다.

import sys, copy

input = sys.stdin.readline

n = int(input())
dp_max = [list(map(int, input().split())) for _ in range(n)]

dp_min = copy.deepcopy(dp_max)

for i in range(1, n):
    # 0
    dp_max[i][0] += max(dp_max[i - 1][0], dp_max[i - 1][1])
    dp_min[i][0] += min(dp_min[i - 1][0], dp_min[i - 1][1])
    # 1
    dp_max[i][1] += max(dp_max[i - 1])
    dp_min[i][1] += min(dp_min[i - 1])
    # 2
    dp_max[i][2] += max(dp_max[i - 1][1], dp_max[i - 1][2])
    dp_min[i][2] += min(dp_min[i - 1][1], dp_min[i - 1][2])

print(max(dp_max[n - 1]), min(dp_min[n - 1]))

# arr과 똑같은 배열 만들고 거기까지 가는 비용 저장
# 해당 점에 도달할때 최대값 1층->2층까지 비용 계산, 1->2층 + 2->3층 계산...

 

2096번 내려가기 문제는 누적 이동 비용과 다음 층으로 이동하기 위한 비용 딱 두개만 기억하면 된다.

층별로 3 칸이 필요하니 길이가 3인 배열 2개만 있다면 충분히 해결할 수 있다는 뜻이다.

import sys

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

dp_max, dp_min = [0] * 3, [0] * 3

for i in range(n):
    a, b, c = map(int, input().split())
    tmp_max, tmp_min = [a, b, c], [a, b, c]

    # 0
    tmp_max[0] += +max(dp_max[0], dp_max[1])
    tmp_min[0] += +min(dp_min[0], dp_min[1])
    # 1
    tmp_max[1] += max(dp_max)
    tmp_min[1] += min(dp_min)
    # 2
    tmp_max[2] += max(dp_max[1], dp_max[2])
    tmp_min[2] += min(dp_min[1], dp_min[2])

    for j in range(3):
        dp_max[j], dp_min[j] = tmp_max[j], tmp_min[j]

print(max(dp_max), min(dp_min))