algospot JUMPGAME

문제 링크입니다: https://algospot.com/judge/problem/read/JUMPGAME

알고리즘 자체는 쉬운데 문제의 제약 내에 코드를 작성하는 것이 정말 어렵다는 것을 깨달았습니다.

/*

게임판의 왼쪽 위 칸에서 시작해서 게임판의 맨 오른쪽 아래 칸에 도착할 수 있는지를 판별하는 프로그램

칸에 적혀 있는 숫자만큼 오른쪽 혹은 밑으로 내려갈 수 있습니다.

*/

#include <iostream>

#include <cstring>

using namespace std;

 

int board[100][100];

int cache[100][100];

 

int jump(int y, int x, int max_size)

{

        //기저 사례:게임판 밖을 벗어난 경우

        if (y == max_size - 1 && x == max_size - 1) //출구

               return 1;

        if (y >= max_size || x >= max_size)

               return 0;

        //메모이제이션

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

        if (result != -1)

               return result;

        return result = (jump(y + board[y][x], x, max_size) || jump(y, x + board[y][x], max_size));

}

 

int main(void)

{

        int test_case, max_size;

        scanf("%d", &test_case);

        if (test_case < 0 || test_case>50)

               exit(-1);

 

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

        {

               scanf("%d", &max_size);

               if (max_size < 2 || max_size>100)

                       exit(-1);

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

 

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

                       for (int k = 0; k < max_size; k++)

                              scanf("%d", &board[j][k]);

 

               if (jump(0, 0, max_size) == 1)

                       printf("YES\n");

               else

                       printf("NO\n");

        }

        return 0;

}

 

 

개발환경:Visual Studio 2017

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

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략