🔗 링크

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

✏️ 문제

강을 사이에 두고 다리를 놓을 수 있는 지점이 주어졌을 때 다리를 놓는 방법의 개수를 구하는 문제입니다.

다리는 서로 겹칠 수 없습니다.

🧠 접근

먼저 문제를 단순화해 봅시다.

다리를 서로 겹치게 놓을 수 없으므로 강 왼쪽에 3개의 사이트, 오른쪽에 4개의 사이트가 있다고 하면 다리를 놓는 방법은 아래 4가지가 있습니다.

1, 2, 3
1, 2, 4
1, 3, 4
2, 3, 4

여기서 다리를 겹치게 놓을 수 없다는 점이 힌트로, 다리 왼쪽의 사이트 개수가 m, 오른쪽의 사이트 개수가 n이라고 하면 다리를 놓는 방법의 개수는 n개 중에서 m개를 순서 상관 없이 뽑는 방법의 개수와 같습니다.

이를 수식으로 표현하면

이고, 수식에 대입만 하면 됩니다!

팩토리얼이 너무 커요

하지만 뭔가 이상합니다. 수식에 팩토리얼이 포함되어 있어 만약 n = 30 이라면 $30!$ 을 계산해야 하는데, $20!$ 만 되더라도 64비트 정수형의 범위를 넘어서기 때문에 Java의 BigInteger 와 같은 편법을 쓰거나 조합의 성질을 활용할 필요가 있습니다.

그런데 $n$ 과 $m$ 이 클 때 굉장히 유용한 조합의 성질이 있습니다.

$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$, $\binom{n}{1} = n$

두 성질을 이용하면 조합을 일일이 계산할 필요 없이 구할 수 있게 됩니다.

즉, 아래와 같은 형태가 됩니다.

final int MAX = 30;

int[][] dp = new int[MAX + 1][MAX + 1];
        
// 초깃값을 채움 (m개 중에 하나만 고를 때)
for (int i = 1; i <= MAX; i++) 
	dp[i][1] = i;
        
for (int j = 2; j <= MAX; j++) 
     for (int k = 2; k <= MAX; k++) 
     	dp[j][k] = dp[j - 1][k - 1] + dp[j - 1][k];

위 배열에 1에서 30까지에 해당하는 모든 조합의 값이 들어가므로 배열에서 적절히 출력해 주면 끝납니다.

📄 전체 소스 코드

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

public class Main {
    private final static int MAX = 30;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(reader.readLine());
        int[][] dp = new int[MAX + 1][MAX + 1];
            
        for (int i = 1; i <= MAX; i++) {
            dp[i][1] = i;
        }

        for (int j = 2; j <= MAX; j++) {
            for (int k = 2; k <= MAX; k++) {
                dp[j][k] = dp[j - 1][k - 1] + dp[j - 1][k];
            }
        }
        
        for (int i = 0; i < testCase; i++) {
            int[] input = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int n = input[1];
            int r = input[0];
            
            System.out.println(dp[n][r]);
        }
    }
}