백준 1890번 점프 // C++

문제

점프

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

출력

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 (2^63)-1보다 작거나 같다.

---

풀이

bfs로 탐색해서 풀었더니, 메모리 초과가 발생하였다. 이 문제는 DP를 이용해서 풀어야한다.

 

따라서, (1,1)부터 각 칸을 가는 경우의 수를 다른 배열에 저장해나가면서, 최종 (n,n) 칸에 도달하면 된다.

 

(x,y) 칸으로 가는 경우의 수는, (x,y)로 이동할 수 있는 칸의 경우의 수들의 합이다.

 

위와 같은 경우, X 칸에 들어갈 수는 Array에서 X 칸으로 이동할 수 있는 (3,2) 칸과 (2,3) 칸의 Count의 합인 6이 된다.

 

이렇게 모든 값을 구하면 정답을 구할 수 있다.

코드

---

#include <iostream>
#include <queue>

using namespace std;

void solve();
void input(int *n, int arr[][101]);

int main(){
    solve();

    return 0;
}

void solve(){
    int n, arr[101][101];
    long long count[101][101] = { 0, };

    input(&n, arr);

    count[1][1] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == n && j == n)
                break;

            // 오른쪽으로 이동
            if (j + arr[i][j] <= n) {
                count[i][j + arr[i][j]] += count[i][j];
            }

            // 아래로 이동
            if (i + arr[i][j] <= n) {
                count[i + arr[i][j]][j] += count[i][j];
            }
        }
    }

    cout << count[n][n];
}

void input(int *n, int arr[][101]){
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> *n;

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