[Algorithm/C++17] 백준 2096 내려가기

문제

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

2096번: 내려가기

풀이 방법

이전 위치 + 현재 위치의 정보를 바탕으로 다음 줄로 계속해서 내려갔을 때 최소 점수와 최대 점수를 구하는 문제다.

DP를 이용해서 풀어야한다는 것을 알 수 있지만, 모든 줄의 정보를 저장하면 메모리 초과가 발생한다.

 

처음엔 int dp[2][100001][3]으로 했었는데 메모리 초과가 발생했다. 단순히 계산해보면

2 * 3 * 100,001 + 3 * 100,001 = 대략 900,000개의 정수이기 때문에 그래도 아슬아슬하게 통과할 줄 알았는데 아니였다.

 

이렇게 모든 줄의 정보를 저장할 필요 없이, 현재 줄을 계산할 때 이전 줄의 정보만 필요하기 때문에   

int dp[2][2][3]을 이용해 문제를 푼다.

 

dp[0][][]에는 최소값들을, dp[1][][]에는 최대값을 저장한다.

dp[][0][]은 이전 줄의 정보, dp[][1][]은 현재 줄의 정보를 저장한다.

최대값과 최소값 계산이 끝나면 dp[][1][]을 dp[][0][]에다 옮겨 다음 계산에 사용할 수 있게 한다.

 

이렇게 하면 메모리 초과는 해결되는데, 100%에서 틀렸다고 나온다.

내 경우는 N=1일 때 틀린 답을 출력하고 있었기 때문이었다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int dp[2][2][3];
int v[100001][3];
int main()
{
    int N;
    scanf("%d", &N);
    for(int i=0; i<N; i++)
    {
        scanf("%d %d %d", &v[i][0], &v[i][1], &v[i][2]);
    }
    dp[0][0][0] = v[0][0];
    dp[0][0][1] = v[0][1];
    dp[0][0][2] = v[0][2];
    dp[1][0][0] = v[0][0];
    dp[1][0][1] = v[0][1];
    dp[1][0][2] = v[0][2];
    
    int minAnswer = min({v[0][0], v[0][1], v[0][2]});
    int maxAnswer = max({v[0][0], v[0][1], v[0][2]});
    for(int i=1; i<N; i++)
    {
        // 최소값 계산
        dp[0][1][0] = min(dp[0][0][0] + v[i][0], dp[0][0][1] + v[i][0]);
        dp[0][1][1] = min({dp[0][0][0] + v[i][1], dp[0][0][1] + v[i][1], dp[0][0][2] + v[i][1]});
        dp[0][1][2] = min(dp[0][0][1] + v[i][2], dp[0][0][2] + v[i][2]);
        
        // 최대값 계산
        dp[1][1][0] = max(dp[1][0][0] + v[i][0], dp[1][0][1] + v[i][0]);
        dp[1][1][1] = max({dp[1][0][0] + v[i][1], dp[1][0][1] + v[i][1], dp[1][0][2] + v[i][1]});
        dp[1][1][2] = max(dp[1][0][1] + v[i][2], dp[1][0][2] + v[i][2]);
        
        minAnswer = min({dp[0][1][0], dp[0][1][1], dp[0][1][2]});
        maxAnswer = max({dp[1][1][0], dp[1][1][1], dp[1][1][2]});
        
        dp[0][0][0] = dp[0][1][0];
        dp[0][0][1] = dp[0][1][1];
        dp[0][0][2] = dp[0][1][2];
        dp[1][0][0] = dp[1][1][0];
        dp[1][0][1] = dp[1][1][1];
        dp[1][0][2] = dp[1][1][2];
    }
    
    /* TEST
    for(int i=0; i<N; i++)
    {
    	printf("%d %d %d\n", dp[0][i][0], dp[0][i][1], dp[0][i][2]);
    }
    printf("\n");
    for(int i=0; i<N; i++)
    {
    	printf("%d %d %d\n", dp[1][i][0], dp[1][i][1], dp[1][i][2]);
    }
    printf("\n");
    */
    printf("%d %d", maxAnswer, minAnswer);
    return 0;
}

고찰

줄에 써져있는 숫자도 마찬가지로 최소값, 최대값 계산할 때는 일일이 다 들고 있을 필요가 없어보인다.

따라서 입력받자마자 계산해주고 다음값 입력받고 하는 식으로 하면 메모리를 최소한으로 사용할 수 있을 것이다.