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

백준의 내려가기(2096) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 처음에 엄청 쉽게 풀었던 문제인데, 계속해서 메모리초과가 뜬 문제이다.

   접근방식은 이렇다. 위에서 부터 한줄씩 내려오는데, 1번 값을 선택할 경우, 그 윗줄에서 1번과 2번을 선택했을 때의 최댓값 +

   1번값을 선택하는 경우, 2번 값을 선택할 경우 ,그 윗줄에서 1, 2, 3번을 선택했을 때의 최댓값 + 2번값을 선택하는 경우,

   3번 값을 선택할 경우, 그 윗줄에서 2번과 3번을 선택했을 때의 최댓값 + 3번값을 선택하는 경우.. 뭐 이런식으로 구현을 했었다.

   물론 위에서 말한 방식은 최댓값을 구하는 방법이다. 최소값은 반대로 구현해야 한다. 하지만, 자바에서는 이 방법으로 통과를

   받을 수 있지만, C++에서는 메모리 초과를 받게된다.

   위에서 말한 방식에서는, 총 3개의 배열이 사용된다.

   MAP[100001][3] = 우리가 입력받는 값을 저장하는 2차원 배열

   Max_DP[100001][3] = i번째 줄 까지의 최댓값을 저장하는 2차원 배열

   Min_DP[100001][3] = i번째 줄 까지의 최솟값을 저장하는 2차원 배열

   하지만 메모리 초과 ! 따라서, 생각을 바꿔서 Max_DP와 Min_DP 2차원 배열의 값을

   Max_DP[2][3], Min_DP[2][3]만 사용해주었다. 어떻게 100001 칸이 2칸이 되었을까???

   생각해보자. 우리가 각 줄에서의 최댓값을 계속해서 저장해둘 메모리를 사용할 필요가 있을까 ??

   예를 들어서, 맵이 총 5줄로 이루어져있다고 생각해보자.

   그렇다면, 우리가 3번째 줄에서 1번값을 선택했을 때의 최댓값 혹은 뭐 2번째 줄에서 3번값을 선택했을 때의 최댓값 이러한

   값들을 마지막까지 가지고 있어야할까?? 아니다. 그렇지 않다.

   3번째 줄에서 1번값을 선택했을 때의 최댓값은, 4번째 줄에서의 최댓값을 구할 때만 사용되므로 잠시만 저장해두면 될 뿐,

   절대로 끝까지 가지고 있을 필요가 없다.

   따라서 Max_DP[2][3], Min_DP[2][3]으로 바꿔주었는데 각각의 의미를 알아보자.

   Max_DP[1][0] = MAP[i][0] + Bigger(Max_DP[0][0], Max_DP[0][1]);
   Max_DP[1][1] = MAP[i][1] + Bigger(Max_DP[0][0], Bigger(Max_DP[0][1], Max_DP[0][2]));
   Max_DP[1][2] = MAP[i][2] + Bigger(Max_DP[0][1], Max_DP[0][2]);

   Max_DP[1][~]는 이전까지의 최댓값들을 비교해서, 최댓값을 알아내는 역할이다.

   Max_DP[0][~]는 Max_DP[1][~]가 알아온 최댓값을 이 후 연산에서 사용하기 위해서 저장해주는 배열이다.

   즉, 코드가 이런식으로 진행이 된다.

    위의 코드에서 i값이 각 줄을 의미한다. Max_DP[1][~]에서는 ~에 들어가는 번호에 따른 최댓값을 알아오고,

    Max_DP[0][~] 에서는 그값을 다음 연산에서 사용하기 위해서 저장해주는 역할이다.

    즉, K번째 줄을 계산한다고 가정했을 때, Max_DP[0][x]에는 "K-1번째 줄에서 x번을 선택했을 때의 최댓값" 이 저장되어 있는

    셈이다. 이 후, K번이 진행이 완료된다면, Max_DP[0][x]에는 "K번째 줄에서 x번을 선택했을 때의 최댓값"으로 갱신될 것이다.

    즉, 우리는 중간중간에 존재하는 모든 최댓값들을 모두 저장해놓을 필요가 없다.

 

    Min_DP도 같은 방식으로 진행된다. 단지, 비교하는 값이 더 작은 값으로, 최소값으로 갱신을 해줄 뿐이다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 100001
using namespace std;
 
int N;
int MAP[MAX][3];
int Max_DP[2][3];
int Min_DP[2][3];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Solution()
{
    Min_DP[0][0] = Max_DP[0][0] = MAP[1][0];
    Min_DP[0][1] = Max_DP[0][1] = MAP[1][1];
    Min_DP[0][2] = Max_DP[0][2] = MAP[1][2];
 
    for (int i = 2; i <= N; i++)
    {
        Max_DP[1][0] = MAP[i][0] + Bigger(Max_DP[0][0], Max_DP[0][1]);
        Max_DP[1][1] = MAP[i][1] + Bigger(Max_DP[0][0], Bigger(Max_DP[0][1], Max_DP[0][2]));
        Max_DP[1][2] = MAP[i][2] + Bigger(Max_DP[0][1], Max_DP[0][2]);
 
        Max_DP[0][0] = Max_DP[1][0];
        Max_DP[0][1] = Max_DP[1][1];
        Max_DP[0][2] = Max_DP[1][2];
 
        Min_DP[1][0] = MAP[i][0] + Min(Min_DP[0][0], Min_DP[0][1]);
        Min_DP[1][1] = MAP[i][1] + Min(Min_DP[0][0], Min(Min_DP[0][1], Min_DP[0][2]));
        Min_DP[1][2] = MAP[i][2] + Min(Min_DP[0][1], Min_DP[0][2]);
 
        Min_DP[0][0] = Min_DP[1][0];
        Min_DP[0][1] = Min_DP[1][1];
        Min_DP[0][2] = Min_DP[1][2];
    }
    
    int Max_Value = Bigger(Max_DP[0][0], Bigger(Max_DP[0][1], Max_DP[0][2]));
    int Min_Value = Min(Min_DP[0][0], Min(Min_DP[0][1], Min_DP[0][2]));
 
    cout << Max_Value << " " << Min_Value << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}