백준 1890 점프 (Java)

목차

• 문제명
• 문제풀이
• 코드

 

백준 1890 점프

 

문제 유형 : 다이나믹 프로그래밍 (DP, Dynamic Programming )

난이도 : 실버 1

 

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

13904번: 과제

 

문제

 

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

 

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

 

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

 

입력

 

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

 

출력

 

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다.

 

 

 

문제 풀이

 

dp 문제로 bottom - up 방식으로 문제를 풀었습니다.

 

dp[r][c]의 의미는 시작점에서 좌표 r, c까지의 경로의 수를 의미합니다. 

 

 

게임판이 아래와 같을 경우

1	1
1	1

 

2차원 배열 dp는 아래와 같을 것입니다.

1	1
1	2

 

왜나하면 1행 1열에서 1행 2열로 가는 경로는 1개

1	1
1	2

 

1행 1열에서 2행 1열로 가는 경로도 1개

1	1
1	2

 

2행 2열로 가는 경로는 위, 아래 경로를 합해서 2임을 알 수 있습니다.

1	1
1	2

 

이를 조금 더 확장해서 게임판이 아래와 같을 경우

1	1	1
1	1	1
1	1	1

 

위와 같은 원리로 dp는 아래와 같이 계산할 수 있습니다.

1	1	1
1	2	3
1	3	6

 

이를 통해 각 좌표에 대해 위로 1 ~ 9 거리, 왼쪽으로 1 ~ 9 거리의 좌표를 탐색해서 해당 좌표의 값과 현재 좌표와의 거리가 같다면 해당 좌표의 dp값을 현재 좌표에 더해 dp[r][c]값을 계산할 수 있습니다.

 

 

코드

 

경로의 개수는 2^63 - 1 개보다 작으므로 long으로 저장해야 오류가 발생하지 않습니다.

 

int -> 4바이트 자료형으로 최대 2^32 - 1 (2,147,483,637) 까지 저장

long -> 8바이트 자료형으로 최대 2^63 - 1 (9,223,372,036,854,775,807) 까지 저장

 

import java.io.*;
import java.util.*;

public class Main {

    static int N;
    static int [][] mat;
    static long [][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        mat = new int[N + 1][N + 1];
        dp = new long[N + 1][N + 1];

        for (int r = 1 ; r < N + 1 ; r++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int c = 1 ; c < N + 1 ; c++) {
                mat[r][c] = Integer.parseInt(st.nextToken());
            }
        }

        dp[1][1] = 1;

        for (int r = 1 ; r < N + 1 ; r++) {
            for (int c = 1 ; c < N + 1 ; c++) {
                // 위 탐색
                int len = 1;
                for (int row = r - 1 ; row >= 1 ; row--) {
                    if (mat[row][c] == len) {
                        dp[r][c] += dp[row][c];
                    }
                    len++;
                }

                // 왼쪽 탐색
                len = 1;
                for (int col = c - 1 ; col >= 1 ; col--) {
                    if (mat[r][col] == len) {
                        dp[r][c] += dp[r][col];
                    }
                    len++;
                }
            }
        }

        System.out.println(dp[N][N]);
    }
}

 

 

마무리