[백준] 1890번 - 점프

백준 1890번 문제 보기

문제풀이

2차원 배열에서의 DP문제이므로

• DP를 위한 배열을 따로 만들고
• 해당 DP 배열을 채워나가는 식으로 풀면 된다.

1520번과 비슷하지만 좀 더 쉽게 풀 수 있는 문제인 것 같다.

Bottom-up 방식으로 풀기

board의 (x, y) 번째 칸으로는 (x, y)의 왼쪽, 위쪽으로 만들어지는 직사각형에 속해있는 칸에서만 올 수 있다.
따라서 (0,0)부터 오른쪽 방향으로 한 칸씩 이동하면서, (그 후 그 다음 행에서 오른쪽 방향으로 이동하면서) 점프를 해서 갈 수 있는 곳에 횟수를 더해주면서 dp 배열을 만들면 된다.

---

Code

#include <iostream>
using namespace std;

int N;
int board[100][100];
long long dp[100][100];

int main(){
    dp[0][0]=1;
    cin >> N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++) cin >> board[i][j];
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(dp[i][j]!=0){
                if(board[i][j]==0) continue;
                if(j+board[i][j]<N){
                    dp[i][j+board[i][j]]+=dp[i][j];
                }
                if(i+board[i][j]<N){
                    dp[i+board[i][j]][j]+=dp[i][j];
                }
            }
        }
    }
    cout << dp[N-1][N-1];
    return 0;
}