[백준] 3372 보드 점프 - Dynamic Programming / Java

graycode 2023. 12. 4. 15:27

• 문제 링크

3372번: 보드 점프

N × N 게임 보드에 양의 숫자들이 적혀있다. 목적은 왼쪽 위에서 오른쪽 아래까지 규칙에 맞게 점프를 해서 가는 것이다. 숫자들은 현재 점에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나

www.acmicpc.net

• 풀이 코드

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = read();
        int[][] mat = new int[n][n];
        BigInteger[][] cnt = new BigInteger[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                mat[i][j] = read();
                cnt[i][j] = BigInteger.ZERO;
            }
        }

        cnt[0][0] = BigInteger.ONE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) continue;

                int k = mat[i][j];
                if (i + k < n) cnt[i + k][j] = cnt[i + k][j].add(cnt[i][j]);
                if (j + k < n) cnt[i][j + k] = cnt[i][j + k].add(cnt[i][j]);
            }
        }

        bw.write(String.valueOf(cnt[n - 1][n - 1]));
        bw.flush();
    }

    private static int read() throws IOException {
        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);

        return n;
    }

}