[C++] 내려가기 (백준 2096번)

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

 

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

int const INTMAX = 1000000000;
int const MAX_N = 100000;
int m[MAX_N][3];
int dpmax[2][3];
int dpmin[2][3];

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

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> m[i][j];
        }
    }

    for (int j = 0; j < 3; j++) {
        dpmax[0][j] = m[0][j];
        dpmin[0][j] = m[0][j];
    }

    for (int i = 1; i < n; i++) {
        dpmax[1][0] = max(dpmax[0][0], dpmax[0][1]) + m[i][0];
        dpmax[1][1] = max(max(dpmax[0][0], dpmax[0][1]), dpmax[0][2]) + m[i][1];
        dpmax[1][2] = max(dpmax[0][1], dpmax[0][2]) + m[i][2];

        dpmin[1][0] = min(dpmin[0][0], dpmin[0][1]) + m[i][0];
        dpmin[1][1] = min(min(dpmin[0][0], dpmin[0][1]), dpmin[0][2]) + m[i][1];
        dpmin[1][2] = min(dpmin[0][1], dpmin[0][2]) + m[i][2];

        for (int j = 0; j < 3; j++) {
            dpmax[0][j] = dpmax[1][j];
            dpmin[0][j] = dpmin[1][j];
        }
    }

    cout << max(max(dpmax[0][0], dpmax[0][1]), dpmax[0][2]) << ' ';
    cout << min(min(dpmin[0][0], dpmin[0][1]), dpmin[0][2]) << '\n';
}

처음에는 dp 배열을 n * 3으로 선언했었는데 메모리 초과가 났었다. (MLE) 생각해보니 dp 배열에서 모든 정보가 필요한 게 아니라 바로 직전의 정보만 필요하기 때문에 dp 배열의 크기를 확 줄일 수 있다. (직전 정보와 현재 정보만 저장하도록) 그렇게 하면 메모리 초과를 해결할 수 있다. (AC)

그리고 min, max로 비교할 수 있는 수가 2개라는 걸 처음 알았다..! 3개 이상의 수를 비교하려면 중첩해서 사용하면 된다.