1890

백준 1890번

Link: 1890번: 점프

---

문제 설명

오늘도 DP문제.

옆에서 친구가 풀던거 같이 한번 풀어봤는데, 조금 고전했다.

처음에는 BFS로 풀어보려고 했는데 문제 자체가 BFS로 풀기에는 조건이 적당하지 않아서 무한루프로 끝났다.

다른 방법으로 풀 수 있는지 찾아보던 중 어떻게든 규칙을 찾아서 DP로 풀어야겠다는 생각을 했고, 고민끝에 규칙을 찾아 샘플 케이스를 돌려보니 맞았다.

구현하는데 인덱스가 헷갈려서 살짝 애먹긴 했지만 무난히 맞았다.

---

정답 코드

//
// Created by Keith_Lee on 26/02/2019.
//

#include <iostream>

using namespace std;

int N;

int map[101][101] = {-1, };
long long DP[101][101] = {0, };

int main(){
    cin >> N;

    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> map[i][j];
        }
    }

    DP[1][1] = 1;

    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(i == j && i == 0){
                continue;
            }

            for(int k=0; k<j; k++){
                if(k + map[i][k] == j){
                    DP[i][j] += DP[i][k];
                }
            }

            for(int k=0; k<i; k++){
                if(k + map[k][j] == i){
                    DP[i][j] += DP[k][j];
                }
            }
        }
    }

//    for(int i=1; i<=N; i++){
//        for(int j=1; j<=N; j++){
//            cout << DP[i][j] << ' ';
//        }
//        cout << '\n';
//    }

    cout << DP[N][N] << '\n';
}

---