[Algorithm] 백준 2096 내려가기 - C++, DP, DFS

2096번: 내려가기

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

int n;
int map[100001][4];
int maxVal[3][4];
int minVal[3][4];

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> map[i][0] >> map[i][1] >> map[i][2];
    
    // solve
    maxVal[0][0] = minVal[0][0] = map[0][0];
    maxVal[0][1] = minVal[0][1] = map[0][1];
    maxVal[0][2] = minVal[0][2] = map[0][2];


    for(int i = 1; i < n; i++){
        int left = map[i][0];
        int mid = map[i][1];
        int right = map[i][2];

        maxVal[1][0] = left + max(maxVal[0][0], maxVal[0][1]);
        maxVal[1][1] = mid + max(maxVal[0][0], max(maxVal[0][1], maxVal[0][2]));
        maxVal[1][2] = right + max(maxVal[0][1], maxVal[0][2]);

        minVal[1][0] = left + min(minVal[0][0], minVal[0][1]);
        minVal[1][1] = mid + min(minVal[0][0], min(minVal[0][1], minVal[0][2]));
        minVal[1][2] = right + min(minVal[0][1], minVal[0][2]);

        maxVal[0][0] = maxVal[1][0];
        maxVal[0][1] = maxVal[1][1];
        maxVal[0][2] = maxVal[1][2];

        minVal[0][0] = minVal[1][0];
        minVal[0][1] = minVal[1][1];
        minVal[0][2] = minVal[1][2];

    }

    int totalMax = max(maxVal[0][0], max(maxVal[0][1], maxVal[0][2]));
    int totalMin = min(minVal[0][0], min(minVal[0][1], minVal[0][2]));
    cout << totalMax << " " << totalMin << '\n';
}

---

 DP 문제를 구하다가 우연히 만난 복병. 문제는 메모리로 C++에서 주어지는 메모리가 상당히 작았습니다. 그래서 처음에는 배열을 입력만큼 2개 더 선언했다가 그대로 메모리 초과가 나왔습니다.

 여러 방법을 찾아봤는데 위와 같은 방법으로 해야 DP + DFS로 출이가 되었습니다. dp 없이 변수 6개로 해보려다가 틀렸습니다 많이 맞아버렸네요.