Algorithm) 백준 1890 점프 c++

dp 문제였습니다.

 

방향은 무조건 오른쪽 or 아래밖에 없으니까 2중 for문을 돌면서 dp 배열을 채워주면 됩니다.

dp[1][1]은 시작 칸이니 1로 셋팅해주고 시작합니다.

 

for문을 돌면서 범위 체크 해주시고 dp[i][j]에서 갈 수 있는 칸에 dp[i][j]만큼 더해줍니다. 

for문이 끝나고 dp[n][n]을 출력하면 정답!

 

제가 한가지 실수했던 부분이 있습니다. i와 j의 범위를 1~n으로 했는데 입력이 0~9이기 때문에 dp[i][j]가 자신에게 여러번 더해질 수 있는 것입니다. 그래서 if(arr[i][j]!= 0 && dp[i][j] != 0) 요 조건을 넣어줬습니다!

 

dp로 접근해야겠다는 생각만 하면 어렵지 않게 풀 수 있는 문제였습니다

 

#include <iostream>
using namespace std;

int arr[101][101];
long long dp[101][101];
int n;

void input() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        for(int j=1; j <=n; j++) {
            cin>>arr[i][j];
        }
    }
}

void cal() {
    dp[1][1] = 1;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(arr[i][j]!= 0 && dp[i][j] != 0) {
                if(j+arr[i][j] <= n) {
                    dp[i][j+arr[i][j]]+= dp[i][j];
                }
                if(i+arr[i][j] <= n) {
                    dp[i+arr[i][j]][j] += dp[i][j];
                }
            }
        }
    }
}

void solve() {
    input();
    cal();
    cout<<dp[n][n];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}