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

문제링크 : https://www.acmicpc.net/problem/2096

2096번: 내려가기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int dp[2][3];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    int N, temp0, temp1, temp2; //N과 메모리 절약을 위해 이전 공간 담을 변수
    cin >> N;
    while(N--)
    {
        int a, b, c;
        cin >> a >> b >> c; 
        temp0 = dp[0][0]; //이전 최대값 담기
        temp1 = dp[0][1];
        temp2 = dp[0][2];

        dp[0][0] = max(temp0, temp1) + a; //첫번째 칸 최대값
        dp[0][1] = max({temp0, temp1, temp2}) + b; //두번째 칸 최대값
        dp[0][2] = max(temp1, temp2) + c; //세번쨰 칸 최대값

        temp0 = dp[1][0]; //이전 최소값 담기
        temp1 = dp[1][1];
        temp2 = dp[1][2];

        dp[1][0] = min(temp0, temp1) + a; //첫번째 칸 최소값
        dp[1][1] = min({temp0, temp1, temp2}) + b; //두번째 칸 최소값
        dp[1][2] = min(temp1, temp2) + c; //세번째 칸 최소값
    }

    cout << max({dp[0][0], dp[0][1], dp[0][2]}) << " " << min({dp[1][0], dp[1][1], dp[1][2]});

    return 0;
}

메모리제한이 빡빡한 dp문제이다.

처음에 dp배열을 [2][1000001][3]으로 선언하고 풀었다가 메모리 초과가 발생했다. (max, min / N / 숫자 3개)

이를 위해서 이전 결과값을 이용하는 슬라이딩 윈도우 기법을 이용해야 한다.

 

임시변수 temp를 선언하고 칸이 총 3개이므로 각각에 대해 이전 최대값 및 최소값을 담아준다.

그리고 dp에 이전 (최대값 or 최소값 중) 가장 (큰 or 작은 값)과 현재 값을 저장한다.

 

이전 값을 재활용하므로  dp 배열에 모든 값을 저장하여 비교할 필요가 없어져서 메모리를 대폭 줄일 수 있다.

 

아래는 메모리 초과가 났던 코드이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int dp[2][100001][3];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    int N, a, b, c;
    cin >> N;
    cin >> a >> b >> c;

    dp[0][0][0] = max(a, b); dp[0][0][1] = max({a, b, c}); dp[0][0][2] = max(b, c); //초기 최대값
    dp[1][0][0] = min(a, b); dp[1][0][1] = min({a, b, c}); dp[1][0][2] = min(b, c); //초기 최소값

    for(int i=1; i<N; i++)
    {
        cin >> a >> b >> c;

        dp[0][i][0] = a + max(dp[0][i-1][0], dp[0][i-1][1]); //첫번째 칸 최대값
        dp[0][i][1] = b + max({dp[0][i-1][0], dp[0][i-1][1], dp[0][i-1][2]}); //두번째 칸 최대값
        dp[0][i][2] = c + max(dp[0][i-1][1], dp[0][i-1][2]); //세번째 값 최대값

        dp[1][i][0] = a + min(dp[1][i-1][0], dp[1][i-1][1]); //첫번째 칸 최소값
        dp[1][i][1] = b + min({dp[1][i-1][0], dp[1][i-1][1], dp[1][i-1][2]}); //두번째 칸 최소값
        dp[1][i][2] = c + min(dp[1][i-1][1], dp[1][i-1][2]); //세번째 칸 최소값

    }

    cout << max({dp[0][N-1][0], dp[0][N-1][1], dp[0][N-1][2]}) << " " << min({dp[1][N-1][0], dp[1][N-1][1], dp[1][N-1][2]});

    return 0;
}

dp의 크기가 [2][100001][3] 이므로 C++이 기본으로 메모리 사용하는 1 ~ 2mb 와 600000 * 4 바이트 = 2.4mb를 더하면 주어진 문제의 메모리 제한인 4mb를 초과하게 된다. 

위 내용은 백준의 질문게시판을 통해서 알게되었다.