[BOJ_20152] Game Addiction

설명

---

아래 코드는 (x,y) x < y는 못 가는 것을 적극 활용해서 문제 풀이를 진행하였습니다.

 

위 문제의 키 포인트는 결국 우리가 구하고 싶은 것은 가장 빠른 최단 거리를 구하는 것이 아닌 갈 수 있는 경우의 수를 구하는 것입니다. 따라서, dp의 행, 열을 각각 내가 지금 가진 위치로 부터 들어온 이전의 경우의 수들을 적재하는 배열로 생각하고 풀면 점화식을 구현 할 수 있습니다.

 

코드

---

package BOJ.Dynamic_Programming;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_20152 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine());

        int H = Integer.parseInt(tk.nextToken());
        int N = Integer.parseInt(tk.nextToken());
        int tmp = 0;
        if(H > N){
            tmp = N;
            N = H;
            H = tmp;
        }
        long[][] dp = new long[N + 1][N + 1];
        for (int i = H; i <= N; i++){
            dp[H][i] = 1;
        }
        for (int i = H + 1; i <= N; i++){
            for (int j = i; j <= N; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        System.out.println(dp[N][N]);
    }
}

 

20152번: Game Addiction