20152번. Game Addiction

 

아이디어

두 좌표 간에 최단 거리로 가는 방법은 (H, H) ~ (N, N) 범위 내에서만 움직이는 것이다. 

 

ex) (4, 4) ~ (8, 8)

? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ?

? ? ? ? o o o o o

? ? ? ? o o o o o

? ? ? ? o o o o o

? ? ? ? o o o o o

? ? ? ? o o o o o

 

어차피 해당 범위 내에서만 움직인다면 (0, 0) ~ (4, 4) 랑 똑같으므로 이 점을 활용해서 

배열의 크기를 |H - N| + 1 로 선언한다.

 

추가로 (H, H) ~ (N, N) 으로 가는 경로의 개수나 (N, N) ~ (H, H) 로 가는 경로의 개수나 동일하므로

(0, 0) ~ (|H-N|, |H-N|) 까지 가는 경로의 개수를 구하면 정답이 된다.

 

dp[i][j] 를 (0, 0) 에서 (i, j) 까지 가는 경로의 개수라고 정의한다면 j > i 인 곳은 침수상태이므로

 

1 0 0   0   0

1 1 0   0   0

1 2 2   0   0

1 3 5   5   0

1 4 9 14 14

 

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

 

이라는 점화식을 얻을 수 있다.

 

 

풀이코드

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 {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int H = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int size = Math.abs(H - N) + 1;
        long[][] dp = new long[size][size];
        dp[0][0] = 1;

        for (int i = 1; i < size; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

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