문제 설명

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

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

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

생각해보기

각 자리에 도달하는 경우의 수를 구한다.
DP 재귀로 풀어야 할까도 생각해 보았는데 먼저 생각나는 데로 풀어보았다. 잘 풀렸다.

결괏값이 클 수 있다. long으로 한다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        InputUtil iu = new InputUtil();
        int N = iu.nextInt();
        int[][] arr = new int[N + 1][N + 1];
        for(int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                arr[i][j] = iu.nextInt();
            }
        }
        long[][] cases = new long[N + 1][N + 1];
        cases[1][1] = 1;
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                if(cases[i][j] == 0 || arr[i][j] == 0) continue;
                int jump = arr[i][j];
                if(i+jump <= N) {
                    cases[i+jump][j] += cases[i][j];
                }
                if(j+jump <= N) {
                    cases[i][j+jump] += cases[i][j];
                }
            }
        }
        System.out.println(cases[N][N]);
    }


    public static class InputUtil {
        private final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer st;

        public int nextInt() throws IOException {
            if(st == null || !st.hasMoreTokens()) {
                this.st = new StringTokenizer(br.readLine());
                return nextInt();
            }
            return Integer.parseInt(st.nextToken());
        }
    }
}