[백준 1890] 점프, C++

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

1890번: 점프

 본 문제는 좌측 상단에서 우측 하단으로 이동하는데, 현재 칸에 적힌 만큼 오른쪽 또는 아래로만 이동하여 가는 방법의 수를 출력하는 문제다. 처음 생각난 방법은 BFS를 이용하여 처음 시작 칸에서 갈 수 있는 모은 경우의 수를 이동하고, 우측 하단에 도착하였을 때, 1씩 증가하는 방법을 이용했으나 메모리 초과를 받았다.

#include <cstdio>
#include <queue>
 
using namespace std;
 
int a[101][101];
int dx[] = {1, 0};
int dy[] = {0, 1};
int ans = 0;
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (x == n-1 && y == n-1) {
            ans += 1;
            continue;
        }
        for (int k = 0; k < 2; k++) {
            int nx = x + dx[k]*a[x][y];
            int ny = y + dy[k]*a[x][y];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                q.push(make_pair(nx, ny));
            }
        }
    }
    printf("%d\n", ans);
}

 

따라서, 다른 방법으로 문제를 풀어야한다.

마지막 칸에 도착하는 방법은 위에서 또는 왼쪽에서 오는 방법 밖에 없다. 따라서, 현재 위치에서 위와 왼쪽에서 도착할 수 있는 경우의 수를 확인하면 된다. 점화식은 d[i][j] = ∑d[i][k] (단, j-k = a[i][k] 일때),  ∑d[k][j] (단, i-k = a[k][j] 일때) 로 정의 할 수 있다. 이때, 경로의 개수는 263-1보다 작거나 같기 때문에 long long 의 자료형을 사용해야 한다.

#include <cstdio>
#include <cstring>
 
using namespace std;
 
int a[101][101];
long long d[101][101];
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    memset(d, 0, sizeof(d));
    d[1][1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j == 1) continue;
            for (int k = 1; k < j; k++) {
                if (j - k == a[i][k]) d[i][j] += d[i][k];
            }
            for (int k = 1; k < i; k++) {
                if (i - k == a[k][j]) d[i][j] += d[k][j];
            }
        }
    }
    printf("%lld\n", d[n][n]);
}