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

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

 

왼쪽으로 내려갈 때,

가운데로 내려갈 때,

오른쪽으로 내려갈 때 3가지의 경우의 수에 대하여 각각의 점화식을 세우면 쉽게 풀 수 있다고 생각되는 문제였습니다.

 

풀이

dp[i][j][k] = i번째 행의 j번째 자리일 때 얻을 수 있는 최댓값 or 최솟값(k로 구분, 0은 최댓값 1은 최솟값)

 

 

왼쪽으로 내려갈 수 있는 건,

이전 단계에서 왼쪽에 있을 때와 가운데에 있을 때입니다.

dp[i][0][k] = dp[i-1][0][k] + dp[i-1][1][k]

 

가운데로 내려갈 수 있는 건,

이전 단계에서 왼쪽, 가운데, 오른쪽입니다.

dp[i][1][k] = dp[i-1][0][k] + dp[i-1][1][k] + dp[i-1][2][k]

 

오른쪽으로 내려갈 수 있는 건,

이전 단계에서 가운데와 오른쪽뿐입니다.

dp[i][2][k] = dp[i-1][1][k] + dp[i-1][2][k]

 

 

위와 같은 점화식을 통해 n개의 행에 대해 모두 dp값을 구해주면 쉽게 풀 수 있습니다.

 

 

인줄 알았으나...

문제를 제대로 읽지 않았었습니다.

 

문제를 읽어보면 메모리 제한이 4MB로 굉장히 빠듯하게 되어 있습니다.

이는 dp배열의 크기를 n * 3만큼 만들면 int형(4바이트) * n의 최대치(10^5) * 3가지 경우의 수(3)으로  

메모리 초과가 된다는 뜻입니다!

 

문제를 잘 읽읍시다

 

 

 

 

 

그럼 어떻게 dp배열의 크기를 줄일 수 있을까요?

 

 

여기서 슬라이딩 윈도우의 개념이 사용됩니다.

 

생각해보면 점화식에서는 이번 크기를 구할 때 이전의 값 3개만 있으면

점화식을 문제없이 계산해낼 수 있습니다.

 

한 행의 값을 구하고 그 값을 이전 값으로 저장해놓고, 다시 새로운 행의 값을 구하면 됩니다!

즉, dp배열이 n만큼 존재할 필요가 없다는 뜻입니다!!

 

 

그리고 배열의 차원을 통해 구분했던 최댓값과 최솟값의 경우

따로 인지하기 쉬운 이름으로 변경해주는 게 코드 작성이 헷갈리지 않았습니다.

 

 int first, second, third;
        first = dpMax[0];
        second = dpMax[1];
        third = dpMax[2];

        dpMax[0] = max(first, second) + score[i][0];
        dpMax[1] = max(first, max(second, third)) + score[i][1];
        dpMax[2] = max(second, third) + score[i][2];

위와 같이 dp배열의 값들을 구해주면 메모리초과 없이 답을 구해낼 수 있습니다.

 

 

 

전체 코드

#include <iostream>
#include <algorithm>
using namespace std;

int score[100005][3];
int dpMax[3];
int dpMin[3];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++){
            cin>>score[i][j];
        }
    }

    for(int i = 0; i < 3; i++){
        dpMax[i] = score[1][i];
        dpMin[i] = score[1][i];
    }

    for(int i = 2; i <= n; i++){
        int first, second, third;
        first = dpMax[0];
        second = dpMax[1];
        third = dpMax[2];

        dpMax[0] = max(first, second) + score[i][0];
        dpMax[1] = max(first, max(second, third)) + score[i][1];
        dpMax[2] = max(second, third) + score[i][2];

        first = dpMin[0];
        second = dpMin[1];
        third = dpMin[2];

        dpMin[0] = min(first, second) + score[i][0];
        dpMin[1] = min(first, min(second, third)) + score[i][1];
        dpMin[2] = min(second, third) + score[i][2];
    }

    int myMax = -1;
    int myMin = 1000009;
    for(int i = 0; i < 3; i++){
        myMax = max(myMax, dpMax[i]);
        myMin = min(myMin, dpMin[i]);
    }

    cout<<myMax<<" "<<myMin;
    return 0;
}

 

 

PS

max와 min은 정말 잘 헷갈리는 단어이니 주의하시길 바랍니다..