[백준] 다리 놓기 - 1010번

문제설명

www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

기본아이디어

간단하게 생각하면 M개 중에 N개를 뽑는 경우의 수를 구하면 그걸 N개 순서로 매칭하는 방법은 1개 밖에 없으므로 구한 경우의 수가 바로 정답이 된다.

 

DP방식의 풀이도 있다고 해서 찾아 볼 예정입니다.

구현코드

public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(input.readLine());
 
        factor = new long[31][31];
        for(int test_case = 1; test_case <= T; test_case++){
            StringTokenizer st = new StringTokenizer(input.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            if(M == N) {
                output.append(1+"\n");
                continue;
            }
            long ans = comb(M, N);
            output.append(ans+"\n");
        }
        System.out.println(output);
    }
    static long[][] factor;
    static long comb(int n, int r){
        if(n == r || r == 0){
            return 1;
        }
        if(factor[n][r] != 0)
            return factor[n][r];
        return factor[n][r] = comb(n-1, r-1) + comb(n-1, r);
    }
 

정리, 기억할 내용

1. nCr 구하는 코드 기억해두자.

2. N! 은 Long타입을 사용해도 금방 Overflow 발생한다.