백준 2096 (내려가기) c++

문제

2096번: 내려가기

다음과 같이 n행 3열의 배열이 주어지면

0열은 다음 행의 0열과 1열 중 한곳으로 이동할 수 있습니다.

1열은 다음행의 0열, 1열, 2열 중 한곳으로 이동할 수 있습니다.

2열은 다음행의 1열, 2열로 중 한곳으로 이동할 수 있습니다.

첫행부터 시작해서 마지막행까지 내려가면서 최댓값과 최솟값을 구하는 문제입니다.

 

처음에 단순하게 dp형태로 문제를 해결하였습니다.

int arr[100001][3];
int dpx[100001][3];
int dpn[100001][3];

arr에다가 주어진 배열의 정보를 저장하고 

dpx에다가 최댓값을 저장해가고

dpn에다가 최솟값을 저장하여 아주 간단하게 문제를 해결하였습니다.

하지만 "메모리 초과" 라는 문구가 뜨고 틀렸습니다.

 

주어진 문제의 메모리는 4MB 입니다. 

따라서 조금더 메모리를 사용하지 않으면서 해결하여야 합니다.

 

아이디어는 우리가 dp작업을 할때 모든 행에 대한 최댓값과 최솟값을 저장하게 되면 메모리가 

너무 비효율적이라는 것입니다. 

즉, 마지막 행에 대한 최종 최댓값과 최솟값만이 필요하므로 dp작업을 좀더 간단하게 바꿔줘야 합니다.

int arr[100001][3];
int dpx[2][3];
int dpn[2][3];

위와 비교하면 dpx와 dpn이 1000001이 아니라 2칸으로 줄어들었습니다.

for (int i = 1; i < n; i++) {
    dpx[1][0] = max(dpx[0][0], dpx[0][1]) + arr[i][0];
    dpn[1][0] = min(dpn[0][0], dpn[0][1]) + arr[i][0];
        
    dpx[1][1] = max(dpx[0][0], max(dpx[0][1], dpx[0][2])) + arr[i][1];
    dpn[1][1] = min(dpn[0][0], min(dpn[0][1], dpn[0][2])) + arr[i][1];
 
    dpx[1][2] = max(dpx[0][1], dpx[0][2]) + arr[i][2];
    dpn[1][2] = min(dpn[0][1], dpn[0][2]) + arr[i][2];
 
    
    //다시 dp 최댓값, 최솟값 
    dpx[0][0] = dpx[1][0];
    dpn[0][0] = dpn[1][0];
 
    dpx[0][1] = dpx[1][1];
    dpn[0][1] = dpn[1][1];
 
    dpx[0][2] = dpx[1][2];
    dpn[0][2] = dpn[1][2];
}

핵심은 dp의 최댓값과 최솟값을 계속 갱신해주는 것입니다. 

dpx[0][x] = 이전행에 대한 x열의 최댓값

dpx[1][x] = dpx[0][x] + arr[1][x] (현재 행에 대한 x열의 최댓값)

 

최솟값도 마찬가지 입니다.

이렇게 dp[1][x]에 대한 값을 갱신해주면 마지막에 dp[0][x] = dp[1][x]로 다시 dp[0][x]에 대한 값을

갱신해줍니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
int arr[100001][3];
int dpx[2][3];
int dpn[2][3];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 3; j++)
            cin >> arr[i][j];
 
    dpx[0][0] = arr[0][0];
    dpx[0][1] = arr[0][1];
    dpx[0][2] = arr[0][2];
    dpn[0][0] = arr[0][0];
    dpn[0][1] = arr[0][1];
    dpn[0][2] = arr[0][2];
    
    for (int i = 1; i < n; i++) {
        dpx[1][0] = max(dpx[0][0], dpx[0][1]) + arr[i][0];
        dpn[1][0] = min(dpn[0][0], dpn[0][1]) + arr[i][0];
        
        dpx[1][1] = max(dpx[0][0], max(dpx[0][1], dpx[0][2])) + arr[i][1];
        dpn[1][1] = min(dpn[0][0], min(dpn[0][1], dpn[0][2])) + arr[i][1];
 
        dpx[1][2] = max(dpx[0][1], dpx[0][2]) + arr[i][2];
        dpn[1][2] = min(dpn[0][1], dpn[0][2]) + arr[i][2];
 
        dpx[0][0] = dpx[1][0];
        dpn[0][0] = dpn[1][0];
 
        dpx[0][1] = dpx[1][1];
        dpn[0][1] = dpn[1][1];
 
        dpx[0][2] = dpx[1][2];
        dpn[0][2] = dpn[1][2];
    }
    cout << max(dpx[0][0], max(dpx[0][1], dpx[0][2])) << ' ' << min(dpn[0][0], min(dpn[0][1], dpn[0][2]));
    return 0;
}