[백준] 1890번: 점프 / C++

✏️ 문제 링크

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

1890번: 점프

 

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

✏️ 문제 풀이

1. DP를 0으로 초기화 해준다. 

2. (0,0)에서 시작하며 DP[0][0]은 1로 초기화해준다. 

3. 만약 DP[i][j]가 1이상이라면 해당 칸의 값 만큼 오른쪽과 아래로 이동시킨다. (이동 가능한 경우에) 

if(DP[i][j]){
   int rx=i; int ry=j+gameBoard[i][j];
   int dx=i+gameBoard[i][j]; int dy=j;
   if(ry<N) DP[rx][ry]+=DP[i][j];
   if(dx<N) DP[dx][dy]+=DP[i][j];
}

4. 그냥 1만 더하는게 아니라 DP[i][j]를 더하는 이유는 해당 경로를 지나가는 경우가 여러가지일 수 있기 때문이다. 

 

✏️ 문제 코드

#include <bits/stdc++.h>

using namespace std;
#define MAX 101

int gameBoard[MAX][MAX];
long DP[MAX][MAX];
int N;

void f(int x, int y){
    DP[0][0]=1;
   for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) {
            if(i==N-1 && j==N-1) return ;
            if(DP[i][j]){
                int rx=i; int ry=j+gameBoard[i][j];
                int dx=i+gameBoard[i][j]; int dy=j;
                if(ry<N) DP[rx][ry]+=DP[i][j];
                if(dx<N) DP[dx][dy]+=DP[i][j];
            }
        }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin>>N;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) {cin>>gameBoard[i][j]; DP[i][j]=0;}
            
    f(0,0);
    
    cout<<DP[N-1][N-1]<<"\n";
    return 0;
    
}

 

 

 

 ⭐ if feedback and question : comment please⭐