[백준] 20152 Game Addiction - Java

 

 

 

고등학교에서 확률과 통계를 배울 때 자주 볼 수 있는 유형이다.

 

 

 

대충 이런 유형으로 특정 경로를 가면 안되게 설정해놓거나 특정 방향으로만 가야 되는 제약을 걸어두고 최단 경로의 수를 구하는 문제..

 

 

 

 

 

 

 

이 문제도 이전 결과를 사용하는 다이나믹 프로그래밍으로 해결할 수 있다.

 

 

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static long[][] dp;
    static int H, N;


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                    

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int size = Math.abs(H - N);

        dp = new long[size + 1][size + 1];

        

        for(int i=0; i<size + 1; i++){
            for(int j=0; j<size + 1; j++){

                if(i < j){
                    continue;
                }

                if(i == 0){
                    dp[i][j] = 1;
                }else   

                if(j == 0){
                    dp[i][j] = 1;
                }

                else{
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }     

                
                
            }
        }

        System.out.println(dp[size][size]);


       
    }
}

 

 

 

long타입으로 설정해야 한다.