백준 2096번 내려가기

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

처음에 작성한 코드는 정답은 맞지만 메모리 초과가 발생하는 코드였습니다.

사실 메모리 초과가 발생하지 않는 것이 더 이상한 코드였던 것 같습니다.

/*

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다.

내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다.

그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다.

바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다.

숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오.점수는 원룡이가 위치한 곳의 수의 합이다.

*/

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100000;

 

int N; //줄

 

int board[MAX][3]; //게임판

int bestCache[MAX][3], worstCache[MAX][3];

 

int bestScore(int y, int x)

{

        //기저사례

        if (y == N)

               return 0;

        int &result = bestCache[y][x];

        if (result != -1)

               return result;

        result = 0;

        if (x == 0) //x가 0일 경우 두가지 경우 중 최고점수

        {

               int temp1 = board[y][x] + bestScore(y + 1, x);

               int temp2 = board[y][x] + bestScore(y + 1, x + 1);

               result = temp1 > temp2 ? temp1 : temp2;

        }

        else if (x == 1) //x가 1일 경우 세가지 경우 중 최고점수

        {

               int temp1 = board[y][x] + bestScore(y + 1, x - 1);

               int temp2 = board[y][x] + bestScore(y + 1, x);

               int temp3 = board[y][x] + bestScore(y + 1, x + 1);

               result = temp1 > temp2 ? (temp1 > temp3 ? temp1 : temp3) : (temp2 > temp3 ? temp2 : temp3);

        }

        else if (x == 2) //x가 2일 경우 두가지 경우 중 최고점수

        {

               int temp1 = board[y][x] + bestScore(y + 1, x - 1);

               int temp2 = board[y][x] + bestScore(y + 1, x);

               result = temp1 > temp2 ? temp1 : temp2;

        }

        return result;

}

 

int worstScore(int y, int x)

{

        //기저사례

        if (y == N)

               return 0;

        int &result = worstCache[y][x];

        if (result != -1)

               return result;

        result = 0;

        if (x == 0) //x가 0일 경우 두가지 경우 중 최저점수

        {

               int temp1 = board[y][x] + worstScore(y + 1, x);

               int temp2 = board[y][x] + worstScore(y + 1, x + 1);

               result = temp1 < temp2 ? temp1 : temp2;

        }

        else if (x == 1) //x가 1일 경우 세가지 경우 중 최저점수

        {

               int temp1 = board[y][x] + worstScore(y + 1, x - 1);

               int temp2 = board[y][x] + worstScore(y + 1, x);

               int temp3 = board[y][x] + worstScore(y + 1, x + 1);

               result = temp1 < temp2 ? (temp1 < temp3 ? temp1 : temp3) : (temp2 < temp3 ? temp2 : temp3);

        }

        else if (x == 2) //x가 2일 경우 두가지 경우 중 최저점수

        {

               int temp1 = board[y][x] + worstScore(y + 1, x - 1);

               int temp2 = board[y][x] + worstScore(y + 1, x);

               result = temp1 < temp2 ? temp1 : temp2;

        }

        return result;

}

 

int main(void)

{

        cin >> N;

        if (N<1 || N>MAX)

               exit(-1);

 

        for (int i = 0; i < N; i++)

               for (int j = 0; j < N; j++)

                       cin >> board[i][j];

 

        memset(bestCache, -1, sizeof(bestCache));

        memset(worstCache, -1, sizeof(worstCache));

        int best = bestScore(0, 0);

        int worst = worstScore(0, 0);

        for (int i = 1; i <= 2; i++)

        {

               best = max(best, bestScore(0, i));

               worst = min(worst, worstScore(0, i));

        }

        cout << best << " " << worst << endl;

        return 0;

}

위 코드가 메모리 초과가 발생하는 이유는 캐시 메모리를 너무 크게 잡은 것이 원인이였습니다.

알고리즘을 생각해보면 바로 전 줄의 캐시 메모리만 있다면 해당 줄의 점수를 알아낼 수 있습니다.

따라서 캐시 메모리를 MAX * 3으로 잡는 대신 2 * 3으로 잡아 전 줄과 해당 줄의 캐시 메모리만 저장하도록 하였습니다.

/*

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다.

내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다.

그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다.

바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다.

숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오.점수는 원룡이가 위치한 곳의 수의 합이다.

*/

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100000;

 

int N; //줄

 

int board[MAX + 1][3]; //게임판

int bestCache[2][3]; //직전과 현재 캐시, x의 범위(0~2)

int worstCache[2][3];

 

void printScore(void)

{      

        for (int i = 1; i <= N; i++)

        {

               int curr = i % 2; //현재 줄

               int prev = (i - 1) % 2; //전 줄

               //최고 점수 찾기

               bestCache[curr][0] = max(bestCache[prev][0], bestCache[prev][1]) + board[i][0];

               bestCache[curr][1] = max(max(bestCache[prev][0], bestCache[prev][1]), bestCache[prev][2]) + board[i][1];

               bestCache[curr][2] = max(bestCache[prev][1], bestCache[prev][2]) + board[i][2];

               //최저 점수 찾기

               worstCache[curr][0] = min(worstCache[prev][0], worstCache[prev][1]) + board[i][0];

               worstCache[curr][1] = min(min(worstCache[prev][0], worstCache[prev][1]), worstCache[prev][2]) + board[i][1];

               worstCache[curr][2] = min(worstCache[prev][1], worstCache[prev][2]) + board[i][2];

        }

        cout << max(max(bestCache[N % 2][0], bestCache[N % 2][1]), bestCache[N % 2][2]) << " " << min(min(worstCache[N % 2][0], worstCache[N % 2][1]), worstCache[N % 2][2]) << endl;

}

 

int main(void)

{

        cin >> N;

        if (N<1 || N>MAX)

               exit(-1);

 

        for (int i = 1; i <= N; i++)

               for (int j = 0; j < 3; j++)

                       cin >> board[i][j];

 

        printScore();

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~