백준 1890번. 점프(c++) / DP

DP를 활용한 문제이다.

문제를 보자마자 DP를 이용하면 쉽게 풀 수 있겠다는 생각을 했다.

 

dp라는 2차원배열을 선언하고 -1로 초기화 시켰다.

이렇게 하면 visited배열을 선언하지 않아도 -1값을 가지면 처음 방문한 좌표라는 것을 알 수 있다.

 

그리고 (1, 1)좌표에서 시작해서 top-down방식으로 구현했다.

또한, 문제에서 "경로의 개수는 263-1보다 작거나 같다."라는 조건이 있기 때문에 dp배열을 long long으로 선언했다.

 

코드 첨부(c++)

// 점프
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int n, x, y;
int game[101][101] = {0, };
int dx[4] = {1, 0};
int dy[4] = {0, 1};
long long dp[101][101] = {0, };
 
long long go(int X, int Y)
{
    if(X==n && Y==n){
        return 1;
    }
 
    if(dp[X][Y]==-1){
        dp[X][Y] = 0;
        for(int i=0; i<2; i++){
            int nx = X+game[X][Y]*dx[i];
            int ny = Y+game[X][Y]*dy[i];
            if(1<=nx && nx<=n && 1<=ny && ny<=n){
                dp[X][Y] += go(nx, ny);
            }
        }        
    }
 
    return dp[X][Y];
}
 
int main()
{
    memset(dp, -1, sizeof(dp));
    cin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin>>game[i][j];
        }
    }
 
    //top-down 방식
    x = 1;
    y = 1;
    dp[x][y] = 0;
    for(int i=0; i<2; i++){
        int nx = x+game[x][y]*dx[i];
        int ny = y+game[x][y]*dy[i];
        if(1<=nx && nx<=n && 1<=ny && ny<=n){
            dp[x][y] += go(nx, ny);
        }
    }
 
    cout<<dp[1][1]<<"\n";
 
    return 0;
}

문제 첨부

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

1890번: 점프