[ BOJ ][JAVA][20152] Game Addiction

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

20152번: Game Addiction

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	1024 MB	317	141	130	49.618%

문제

강산이는 심각한 게임 중독자이기 때문에 날씨에 상관없이 매일 PC방을 간다.

최근에 폭우로 인해 일부 지역이 침수되어 침수된 지역으로는 이동할 수 없게 되었다. 하지만 강산이는 출석 이벤트를 위해 하루도 빠짐없이 PC방을 가야 한다.

강산이는 PC방까지 상, 하, 좌, 우 방향으로만 이동하며, 한 번 이동할 때의 거리는 1이다. 또한, 강산이는 게임을 빨리하러 가야 하기 때문에 집에서 PC방까지 최단경로로 움직인다.

강산이의 집의 좌표 (H, H)와 PC방의 좌표 (N, N)이 주어지고 좌표평면 위 (x, y)에서 y > x인 곳은 침수되었다고 할 때, 강산이가 침수된 지역을 피해서 PC방까지 갈 수 있는 경로의 개수를 구하라.

단, PC방의 좌표가 집의 좌표 같은 경우 경로는 1가지라고 한다.

입력

첫째 줄에 집과 PC방의 좌표 (H, H), (N, N) 을 나타내는 두 정수 H, N (0 ≤ H, N ≤ 30) 이 차례로 주어진다.

출력

집에서 PC방까지 갈 수 있는 경로의 개수를 출력한다.

예제 입력 1

8 4

예제 출력 1

14

예제 입력 2

0 3

예제 출력 2

5

접근

(h, h)에서 (n, n)으로 가는 최단 경로 개수 중, y <= x인 경로의 개수를 구한다.
시작점(H, H)를 왼쪽 아래, 목표(N, N)지점을 오른쪽 위라고 가정하고 한다.
그러면 dp는 (왼쪽에서 오는것 + 아래에서 오는 것)이 현재 지점의 경로 개수가 된다.

여기서 dp[i][j] 는 i가 y좌표, j가 x좌표이다.

나올 수 있는 값은 long타입으로 타입 조심하자..

코드

/*
    Game Addiction
    DP
*/
import java.io.*;
import java.util.*;
public class p20152 {
    static long[][] dp;
    static int h, n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        dp = new long[33][33];
        StringTokenizer st = new StringTokenizer(br.readLine());
        h = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        long answer = 0;
        if (h == n) {
            answer = 1;
        } else {
            if (h > n) {
                int tmp = h;
                h = n;
                n = tmp;
            }

            for (int i = h; i <= n; i++) {
                dp[h][i] = 1;
            }

            for (int i = h + 1; i <= n; i++) {
                for (int j = h + 1; j <= n; j++) {
                    // x < y(실제 좌표 법)인 경우는 침투되었으므로 i > j 일때는 continue 해줘야 함
                    if (i <= j) {
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    }
                }
            }
            answer = dp[n][n];
        }

        System.out.println(answer);
    }
}