Beakjoon 1890 점프

20 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/1890

나의 풀이

DP[i][j] = (j,i) 지점에 도달할 수 있는 경우의 수
반드시 오른쪽이나 아래쪽으로만 이동할 수 있으므로 (0,0)부터 순차적으로 탐색하면 방문할 수 있는 모든 경우를 확인할 수 있다.

풀이 코드 : 1890 점프

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

long long DP[100][100];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin>>N;
    vector<vector<int>> score;

    score.resize(N);
    for(int i=0;i<N;i++){
        score[i].resize(N);
        for(int j=0;j<N;j++){
            cin>>score[i][j];
        }
    }

    DP[0][0] = 1;

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(DP[i][j] != 0){
                if(i+score[i][j] < N && score[i][j] != 0)
                    DP[i+score[i][j]][j] += DP[i][j];
                if(j+score[i][j] < N && score[i][j] != 0)
                    DP[i][j+score[i][j]] += DP[i][j];
            }
        }
    }
    
    cout<<DP[N-1][N-1];

}

채점결과