[백준] 2096 내려가기

2096번: 내려가기

 

boj.kr

풀이

전형적인 동적계획법 문제이다. 하지만 이 문제는 메모리 초과를 조심해야한다. 일반적인 동적계획법을 풀 때 처럼 dp 배열을 생성하면 메모리 초과로 오답을 받게 된다. 그래서 아래의 코드에서는 입력받을 때마다 최대값, 최소값을 저장하는 dp 배열을 갱신해줘서 해결했다.

코드

C++

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int dp[3][2];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        int t1 = dp[0][0];
        int t2 = dp[1][0];
        int t3 = dp[2][0]; 
        int t4 = dp[0][1];
        int t5 = dp[1][1];
        int t6 = dp[2][1];
        dp[0][0] = max(t1, t2) + a;
        dp[1][0] = max(max(t1, t2), t3) + b;
        dp[2][0] = max(t2, t3) + c;
        dp[0][1] = min(t4, t5) + a;
        dp[1][1] = min(min(t4, t5), t6) + b;
        dp[2][1] = min(t5, t6) + c;
    }
    int max_value = max(max(dp[0][0], dp[1][0]), dp[2][0]);
    int min_value = min(min(dp[0][1], dp[1][1]), dp[2][1]);
    cout << max_value << ' ' << min_value << '\n';
    return 0;
}

Python3

import sys

n = int(sys.stdin.readline().rstrip())
dp = [[0] * 2 for _ in range(3)]
while n > 0:
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    n -= 1
    t1 = dp[0][0]
    t2 = dp[1][0]
    t3 = dp[2][0]
    t4 = dp[0][1]
    t5 = dp[1][1]
    t6 = dp[2][1]
    dp[0][0] = max(t1, t2) + a
    dp[1][0] = max(max(t1, t2), t3) + b
    dp[2][0] = max(t2, t3) + c
    dp[0][1] = min(t4, t5) + a
    dp[1][1] = min(min(t4, t5), t6) + b
    dp[2][1] = min(t5, t6) + c
max_value = max(max(dp[0][0], dp[1][0]), dp[2][0])
min_value = min(min(dp[0][1], dp[1][1]), dp[2][1])
print(max_value, min_value)