백준 1890번 점프

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

번역이 살짝 아쉬운 문제였습니다.

처음에는 해당 칸에 있는 숫자만큼 움직일 수 있는 경우라고 이해해서 답보다 훨씬 많은 경로를 구했습니다.

문제에 해당 칸에 있는 숫자만큼 "한 방향"으로 움직일 수가 있다고 했더라면 고생하지 않았을 것 같습니다.

답이 2^63 - 1까지 나올 수 있으므로 자료형을 long long으로 선언하는 것이 핵심이였습니다.

/*

N×N 게임판에 수가 적혀져 있다.

이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다.

반드시 오른쪽이나 아래쪽으로만 이동해야 한다.

0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

*/

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100;

 

int N;

int board[MAX][MAX];

long long cache[MAX][MAX]; //최대 2^63 - 1

 

/*

long long path(void)

{

        cache[0][0] = 1; //시작

       

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

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

               {

                       //아래로 갈 수 있고, 움직였을 때 범위 안에 있다면

                       if (i != N - 1 && i + board[i][j] < N)

                              cache[i + board[i][j]][j] += cache[i][j];

                       //오른쪽으로 갈 수 있고,, 움직였을 때 범위 안에 있다면

                       if (j != N - 1 && j + board[i][j] < N)

                              cache[i][j + board[i][j]] += cache[i][j];

               }

        return cache[N - 1][N - 1];

}

*/

 

//재귀

long long path(int y, int x)

{

        if (y == N - 1 && x == N - 1)

               return 1;

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

        if (result != -1)

               return result;

        result = 0;

        //아래로 갈 수 있고, 움직였을 때 범위 안에 있다면

        if (y != N - 1 && y + board[y][x] < N)

               result += path(y + board[y][x], x);

        //오른쪽으로 갈 수 있고,, 움직였을 때 범위 안에 있다면

        if (x != N - 1 && x + board[y][x] < N)

               result += path(y, x + board[y][x]);

        return result;

}

 

int main(void)

{

        cin >> N;

        if (N<4 || N>MAX)

               exit(-1);

 

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

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

                       cin >> board[i][j];

 

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

        //cout << path() << endl;

        cout << path(0, 0) << endl;

        return 0;

}

개발환경:Visual Studio 2017

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

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