[백준 2096] 내려가기 C++

www.acmicpc.net/problem/2096

2096번: 내려가기

 

이번 문제는 다이나믹 프로그래밍 문제로, 기존의 다이나믹 문제 유형과 비슷하지만,

메모리를 효율적으로 구성해야하는 문제입니다.

 

메모리를 효율적으로 사용하기 전에,

기존의 간단한 방법으로 문제를 풀면

 

배열을 arr[n][3] 배열에서 이전의 위치에서 arr[n][0~3]에 더 해질 수 있는 칸들(arr[n-1][0~3] 중에서 최댓값을 구해서 arr[n][0~3]에 더해주면 됩니다.

 

문제에서는 

별
가능	가능	불가능

 

이렇게 나와있어서, 별이 가능한 칸에 움직일 수 있습니다.

이것을 반대로 생각해서

첫 번째 칸에 올 수 있는 별의 위치를 구하면 됩니다. 

즉,

 

O별	O별	X불가능
여기칸에 올 수 있는 별

이렇게 문제를 바꿔서 생각하면 됩니다.

 

메모리가 4MB로 제한이 되어있는데, 메모리 제한만 풀린다면 다음 코드가 정답으로 인정이 될것입니다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;


const int MAX = 100001;

//const int MAX = 10;





void solution(){

    int dp[MAX][3] = {0, };
    int map[MAX][3] = {0, };

    int n;
    
    cin >> n;

    for (int i = 1; i <= n; i++){
        cin >> map[i][0] >> map[i][1] >> map[i][2];
    }

    //max값찾기

    for (int i = 1; i <= n; i++){
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + map[i][0];
        dp[i][1] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2])) + map[i][1];
        dp[i][2] = max(dp[i-1][1], dp[i-1][2]) + map[i][2];
    }

    int maxV = max(dp[n][0], max(dp[n][1], dp[n][2]));

    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++){
        dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + map[i][0];
        dp[i][1] = min(dp[i-1][0], min(dp[i-1][1], dp[i-1][2])) + map[i][1];
        dp[i][2] = min(dp[i-1][1], dp[i-1][2]) + map[i][2];
    }
    
    int minV = min(dp[n][0], min(dp[n][1], dp[n][2]));


    cout << maxV << " " << minV << '\n';
}
int main(){


    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solution();

    return 0;
}

 

 

하지만, 이 코드의 경우,

dp[100001][3]의 메모리를 사용해야하기 때문에 약 4MB 이상의 메모리가 필요합니다.

 

간단하게 위와같이 풀수 있지만, 문제에서 제한 조건은 메모리 4MB이하로 문제를 해결하라고 해서

 

필요 없는 공간 빼고 진짜 필요한 메모리만 잡아서 풀게 된다면 4MB메모리를 사용해서 풀 수 있습니다.

즉, 현재 진행되야하는 메모리 3 공간 + 이전의 진행했던 공간 3이 있으면 됩니다.

max와 min을 한꺼번에 계산하고 싶다면, 현재 진행되어야 하는 메모리 max 3공간 + 현재 진행되어야하는 메모리 min 3공간 + 이전에 진행했던 공간 3공간(temp배열 or 변수)를 선언한다면, 메모리를 엄청나게 줄일 수 있습니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;


void solution(){

    int n;
    int maxV, minV;
    int mind[3] = {0, };
    int maxd[3] = {0, };
    int input[3] = {0, };


    cin >> n;

    cin >> maxd[0] >> maxd[1] >> maxd[2];
    mind[0] = maxd[0];
    mind[1] = maxd[1];
    mind[2] = maxd[2];

    for (int i = 1; i < n; i++){
        cin >> input[0] >> input[1] >> input[2];

        int temp0 = maxd[0];
        int temp1 = maxd[1];
        int temp2 = maxd[2];

        maxd[0] = max(temp0, temp1) + input[0];
        maxd[1] = max(temp0, max(temp1, temp2)) + input[1];
        maxd[2] = max(temp1, temp2) + input[2];

        temp0 = mind[0];
        temp1 = mind[1];
        temp2 = mind[2];

        mind[0] = min(temp0, temp1) + input[0];
        mind[1] = min(temp0, min(temp1, temp2)) + input[1];
        mind[2] = min(temp1, temp2) + input[2];

        

    }

    maxV = max(maxd[0], max(maxd[1], maxd[2]));
    minV = min(mind[0], min(mind[1], mind[2]));

   

    cout << maxV << " " << minV << '\n';
}
int main(){


    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solution();

    return 0;
}