백준 1010번 다리 놓기 (JAVA)

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

1010번: 다리 놓기

 

저는 조합과 DP를 이용해 문제를 해결하였습니다.

저는 강 동쪽의 개수(m)개 중에 강 서쪽(n)개를 뽑으면 된다고 생각했습니다. 이유는 다리는 서로 겹치게 할 수 없기 때문에 순서가 중요하지 않고 m개 중 n개를 뽑아 놓으면 겹치기 않게 하는 경우는 하나이기에 m개 중 n개를 뽑는 경우의 수만 찾으면 된다고 생각했습니다. 이를 조합을 통해 구하였고, 테스트 케이스 마다 조합을 구하기보다 이 값을 dp에 저장하여 문제를 해결하였습니다.

 

package BOJ.dp;

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

public class BOJ_1010 {
    private static final int MAX_VALUE = 30;
    private static final int NOT_VALID = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        StringTokenizer st = new StringTokenizer(br.readLine());
        int testCnt = stoi.apply(st.nextToken());
        int[][] dp = new int[MAX_VALUE+1][MAX_VALUE+1];
        for(int t = 0 ; t < testCnt ; t++){
            st = new StringTokenizer(br.readLine());
            int n = stoi.apply(st.nextToken());
            int m = stoi.apply(st.nextToken());
            int result = comb(m,n,dp);
            System.out.println(result);
        }
    }
    private static final int comb(int n , int r,int[][] dp){
        if(dp[n][r] != NOT_VALID){
            return dp[n][r];
        }
        if(r == 0 || r == n){
            return 1;
        }
        return dp[n][r] = comb(n-1,r,dp) + comb(n-1,r-1,dp);
    }
}