[BOJ-1890] 점프

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

[문제요약]

N * N 게임판에 수가 적혀있다.

가장 왼쪽 위 칸 [0][0] 에서 가장 오른쪽 아래 칸 [N-1][N-1] 으로 규칙에 맞게 점프해서 가는 것이다.

규칙은 아래와 같다.

1. [ROW][COL] 위치에 적혀있는 이동수만큼 이동할 수 있다.
2. 이동은 오른쪽 혹은 아래쪽으로만 이동할 수 있다. (오른쪽+아래쪽 을 섞어 이동할 수 없다.)

[입력]

N ~ [4,100] : 게임판의 크기가 주어진다.

게임판이 주어진다. 각 위치에 이동수가 주어진다. 이동 수 M ~[0,9] 이다.

가장 오른쪽 아래칸에는 0이 주어진다.

[출력]

가장 오른쪽 아래칸으로 이동할 수 있는 모든 경우의 수를 출력한다. 2^63 - 1 보다 작거나 같다.

[접근방법]

입력을 받아 게임판을 저장할 2차원배열 하나와 값을 구할 2차원배열 하나를 만든다.

현재 위치에서 이동할 수 있는 [조건 1,2]를 따라 이동할 dr, dc 를 만들어 루프를 돌면 문제를 풀 수 있다. 

[source C++11 DP]

#include<cstdio>
#define din1(a) scanf("%d", &a)
typedef long long ll;
const int M = 111;
 
int N;
int F;
int imap[M][M];
ll ans[M][M];
int dr[] = { 0, 1 };
int dc[] = { 1, 0 };
 
int main() {
    din1(N);
    F = N - 1;
    ans[0][0] = 1;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) din1(imap[r][c]);
    } // input
 
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            for (int i = 0; i < 2; i++) {
                int tr = r + dr[i] * imap[r][c];
                int tc = c + dc[i] * imap[r][c];
                if (tr >= N || tc >= N) continue;
                if (imap[r][c] == 0) continue;
                ans[tr][tc] += ans[r][c];
            }
        }
    }
    printf("%lld", ans[F][F]);
 
    return 0;
}