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

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

문제 분석

문제 조건

생각보다 단순한 문제다. 행은 N(입력값), 열은 3인 배열에서 이동할 수 있는 제약이 있고 이들의 최대/최소값을 구하는 문제이다. 

문제를 보자마자 무조건 dp겠다 싶었다. 그래서... dp임은 인지했지만, 답이 잘 나왔음에도 메모리가 초과되었다는 것을 보았다.

 

4MB????

🤔: 대체 4MB는 뭐야?! 문제에서는 N의 최대값은 10만인데... 입력값만 받아도 최대 30만 데이터를 저장하는 배열을 만들어야하는데?
이걸 어떻게 풀라는거야...

---

문제 풀이

DP문제를 풀기 위해서는 무조건 이전에 계산했던 최적의 값들을 무조건 저장해둬야한다고 생각했다... 그래서 처음 생각했던 오답풀이는 이러하다...

 

⚠️오답풀이!!!⚠️

☠️ 1. 입력을 무조건 배열로 다받는다...
☠️ 2. 배열의 아래로 내려가면서 dp값으로 최대일 때를 기준으로 가장 아래 행에 최댓값이 쌓이도록 한다.
☠️ 3. 다시 아래에서부터 위로 올라가면서 기존의 입력받았던 배열값을 다시 원복한다. (나름 메모리를 아끼겠다고...)
☠️ 4. 기존 입력값으로 돌아온 배열을 아래로 내려가면서 최소일 때를 기준으로 최솟값이 쌓이도록 한다.

코드 길이도 100줄이 넘고... 참 안좋은 알고리즘이다... Trash..

 

정답 풀이!

💡해당 알고리즘에서는 '최댓값'과 '최솟값'만이 필요하다. 그러니까 중간 계산과정은 저장을 할 필요가 없다는 것이다!

 

자 이게 무슨말이냐. 한줄씩 입력받을 때마다 최대, 최소를 곧바로 계산하고, 다음 입력값을 받으면 이전에 받았던 입력값은 굳이 필요가 없다!!! 이 방식을 알고 DP를 적용해서 문제를 푼다면 매우 쉽게 풀 수 있는 문제이다. (이것만 알아도 거의 실버3문제 수준...)

C++ 풀이

#include <iostream>
#include <vector>

using namespace std;

int minDP[3] = {0};
int maxDP[3] = {0};
int inputDP[3] = {0};

int mini(int x, int y) {
    if(x > y)
        return y;
    return x;
}

int maxi(int x, int y) {
    if(x > y)
        return x;
    return y;
}

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

    int N;
    cin >> N;
    
    int t1, t2, t3;
    
    for(int i=0; i<N; i++) {
        cin >> inputDP[0] >> inputDP[1] >> inputDP[2];
        
        t1 = minDP[0];
        t2 = minDP[1];
        t3 = minDP[2];
        
        //최솟값 기록하기
        minDP[0] = mini(t1, t2) + inputDP[0];
        minDP[1] = mini(mini(t1, t2), t3) + inputDP[1];
        minDP[2] = mini(t2, t3) + inputDP[2];

        //최댓값 기록하기
        t1 = maxDP[0];
        t2 = maxDP[1];
        t3 = maxDP[2];
        
        maxDP[0] = maxi(t1, t2) + inputDP[0];
        maxDP[1] = maxi(mini(t1, t2), t3) + inputDP[1];
        maxDP[2] = maxi(t2, t3) + inputDP[2];
    }

    cout << maxi(maxDP[0], maxi(maxDP[1], maxDP[2])) << ' ' << mini(minDP[0], mini(minDP[1], minDP[2]));
    
    return 0;
}

코드 리뷰는 언제나 환영입니다!