BOJ : 2096 내려가기

---

[BOJ 2096(G4) 리뷰]

전형적인 DP문제처럼 보였으나 메모리 제한이 걸려있다.

가장 쉽게 풀기 위해서는 DP[3][100001]을 선언하며 각 위치에 대해 DP계산을 해주면 되지만

이렇게 하면 불필요한 메모리 공간때문에 메모리 초과를 맞게 된다.

 

따라서 우리는 계산 후 불필요한 데이터는 굳이 메모리에 저장하지 않도록 해야 한다.

그러기 위해서 입력받는 순간 MAX DP, MIN DP값을 계산하며 단계를 거듭할때마다 값을 복사하여 한정된 메모리를 통하여 DP계산이 가능하게 했다.

결국 실질적으로 사용하는 메모리는 MAXDP[2][3], MINDP[2][3]이 된다.

 

---

/*
    20.09.01
    BOJ : 2096 내려가기 (https://www.acmicpc.net/problem/2096)
    다이나믹 프로그래밍
*/
#include <bits/stdc++.h>
using namespace std;

int N;
int maxdp[2][3];
int mindp[2][3];


int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    for (int i = 0; i < 3; i++)
    {
        int val;
        cin >> val;
        maxdp[0][i] = val;
        mindp[0][i] = val;
    }

    if (N == 1)
    {
        cout << max({ maxdp[0][0], maxdp[0][1], maxdp[0][2] }) << ' ' << min({ mindp[0][0], mindp[0][1], mindp[0][2] });
        return 0;
    }

    
    for (int i = 2; i <= N; i++)
    {
        for (int j = 0; j <= 2; j++)
        {
            int val;
            cin >> val;
            if (j == 0)
            {
                maxdp[1][j] = val + max(maxdp[0][j], maxdp[0][j + 1]);
                mindp[1][j] = val + min(mindp[0][j], mindp[0][j + 1]);
            }
            else if (j == 1)
            {
                maxdp[1][j] = val + max({ maxdp[0][j - 1],maxdp[0][j], maxdp[0][j + 1] });
                mindp[1][j] = val + min({ mindp[0][j - 1],mindp[0][j], mindp[0][j + 1] });
            }
            else if (j == 2)
            {
                maxdp[1][j] = val + max(maxdp[0][j], maxdp[0][j - 1] );
                mindp[1][j] = val + min(mindp[0][j], mindp[0][j - 1]);
            }
        }
        for (int j = 0; j <= 2; j++)
        {
            maxdp[0][j] = maxdp[1][j];
            mindp[0][j] = mindp[1][j];
        }
    }


     int maxans = max({ maxdp[1][0],maxdp[1][1],maxdp[1][2] });
     int minans = min({ mindp[1][0],mindp[1][1],mindp[1][2] });
    
    cout << maxans << ' ' << minans;
    
    return 0;
}