1890번: 점프

문제 링크

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

1890번: 점프

 

문제 풀이 코드

#include <iostream>

using namespace std;

const int MN = 101;
long long dp[MN][MN];
int input[MN][MN];

int main(void){

    ios::sync_with_stdio(false); cin.tie(NULL);
    int n; cin>>n;

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int m; cin>>m;
            input[i][j]=m;
        }
    }

    dp[0][0]=1;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(dp[i][j]==0||(i==n-1&&j==n-1)) continue;
            
            if((i+input[i][j])<n) dp[i+input[i][j]][j] += dp[i][j];
            if((j+input[i][j])<n) dp[i][j+input[i][j]] += dp[i][j]; 
            
        }
    }

    cout<<dp[n-1][n-1];
    return 0;
}

 

* 처음 제출 시 틀린 부분

 

dp문제이고 dp배열에 전의 경우의 수가 축적 되기 때문에

if((i+input[i][j])<n) dp[i+input[i][j]][j] += 1;

if((j+input[i][j])<n) dp[i][j+input[i][j]] += 1;

이 아닌

if((i+input[i][j])<n) dp[i+input[i][j]][j] += dp[i][j];

if((j+input[i][j])<n) dp[i][j+input[i][j]] += dp[i][j];

위의 식으로 풀어야한다.