백준 보드점프(3372)

 

오늘은 DP문제를 풀었다

 

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

3372번: 보드 점프

 

 

문제는 크게 어렵지 않다 처음 시작점부터 점프가능한 부분의 영역을 DP해가면서 진행하면된다.

 

크기가 굉장히 큰편이기에 BigInteger를 사용했다.

 

처음에는 모두 0으로 초기화 안하고 NULL체크로 진행했는데 종착점을 0으로 초기화 하지않으면 통과하지 못하는 케이스가 있어 고전했다.

 

알고리즘은 쉽지만 조건이 약간 귀찮은 문제였다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int[][] dir = {
            {0, 1},
            {1, 0}
    };

    public static void main(String[] args) throws IOException {
        solution();
    }


    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[][] map = new int[N][N];
        BigInteger[][] dp = new BigInteger[N][N];

        for (int i=0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j=0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i=0; i < N; i++) Arrays.fill(dp[i], new BigInteger("0"));
        dp[0][0] = new BigInteger("1");

        for (int i=0; i < N; i++) {

            for (int j=0; j < N; j++) {
                if (dp[i][j] == null) continue;
                else if (map[i][j] == 0) continue;

                for (int k=0; k < dir.length; k++) {
                    int x = i + (dir[k][0] *  map[i][j]);
                    int y = j + (dir[k][1] *  map[i][j]);


                    if (x >=0 && y >=0 && x < N && y < N ) {
                        dp[x][y] = dp[x][y].add(dp[i][j]);
                    }
                }
            }
        }

        for (int i=0; i < N; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }

        System.out.println(dp[N-1][N-1]);


    }


}

 

결과