2096번 : 내려가기

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

2096번: 내려가기

 

 

이 문제는, 간단하게 상향식 접근으로 문제를 풀 수 있지만,

 

 

메모리 초과가 계속 발생한다. 따라서, 계속 사용되는 DP 값들만 저장해둬야 한다는 아이디어가 필요하다.

 

 

---

 

 

점화식은 다음과 같이 작성할 수 있다.

 

 

 

R = ROW(1 ~ N)
C = COL(1 ~ 3)

 

 

 

만약 C가 1이고, DP를 R, C까지 온 최댓값이라고 정의하자

 

 

 

DP[R][C} = max(DP[R - 1][0], DP[R - 1][1]) + arr[R][C]

 

 

 

로 정의된다. 

 

 

 

C가 2, 3인 경우도 위와같은 형태로 점화식을 세울 수 있다. 

 

 

 

최소값을 구하는 경우도 위의 형태와 동일하므로 생략!

 

 

 

---

 

 

해설코드(C++).

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
 
using namespace std;
 
int N;
int arr[3];
int dp[2][3][2] = { 0 };
int min_result = 9 * 100000;
int max_result = 0;
 
int main(void) {
    cin >> N;
    for (int i = 0; i < 3; i++) {
        cin >> dp[0][i][0];
        dp[0][i][1] = dp[0][i][0];
    }
 
    // Bottom-Up
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> arr[j];
        }
 
        for (int j = 0; j < 3; j++) {
            if (j == 0) {
                dp[1][0][0] = max(dp[0][0][0], dp[0][1][0]);
                dp[1][0][1] = min(dp[0][0][1], dp[0][1][1]);
            }
            else if (j == 1) {
                dp[1][1][0] = max(max(dp[0][0][0], dp[0][1][0]), dp[0][2][0]);
                dp[1][1][1] = min(min(dp[0][0][1], dp[0][1][1]), dp[0][2][1]);
            }
            else {
                dp[1][2][0] = max(dp[0][1][0], dp[0][2][0]);
                dp[1][2][1] = min(dp[0][1][1], dp[0][2][1]);
            }
            dp[1][j][0] += arr[j];
            dp[1][j][1] += arr[j];    
        }
        
 
        for (int j = 0; j < 3; j++) {
            dp[0][j][0] = dp[1][j][0];
            dp[0][j][1] = dp[1][j][1];
        }
    }
    for (int i = 0; i < 3; i++) {
        max_result = max(max_result, dp[0][i][0]);
        min_result = min(min_result, dp[0][i][1]);
    }
 
    cout << max_result << " " << min_result << endl;
 
    return 0;
}