[백준] 1010번 다리 놓기 (JAVA)

문제

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

1010번: 다리 놓기

 

설명

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다.
한 사이트에는 최대 한 개의 다리만 연결될 수 있고 다리끼리는 서로 겹쳐질 수 없다.

실행결과는 M개의 사이트 중 N개를 순서 구분 없이 고르는 경우의 수를 의미한다.

따라서, 조합을 사용해야 하는데 파스칼의 삼각형을 이용하면 쉽게 구할 수 있다.

파스칼의 삼각형은 \({}_{n}\mathrm{C}_{r} = {}_{n - 1}\mathrm{C}_{r - 1} + {}_{n - 1}\mathrm{C}_{r}\) 인데 원하는 곳까지 dp 배열을 채우면서 가면 된다.

int comb(int n, int r) {
    if (dp[n][r] > 0)
        return dp[n][r];

    if (n == r || r == 0)
        return dp[n][r] = 1;

    return dp[n][r] = comb(n - 1, r - 1) + comb(n - 1, r);
}

 

전체 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int T, N, M;
    static int[][] dp;

    // 조합 공식 이용
    static int comb(int n, int r) {
        if (dp[n][r] > 0)
            return dp[n][r];

        if (n == r || r == 0)
            return dp[n][r] = 1;

        return dp[n][r] = comb(n - 1, r - 1) + comb(n - 1, r);
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());

        dp = new int[30][30];

        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            System.out.println(comb(M, N));
        }
    }
}