[백준 알고리즘] 2407번(조합)

[백준 알고리즘]

지난 번에 팩토리얼에 대해 풀었고 이번에는 조합에 대한 문제입니다.

조합에 대한 문제는 예전에 제가 이항계수 때 풀어놓은 것이 있어서

그것을 이용하여 문제를 해결했습니다.

이번에 조금 다른 것이 있다면 범위 입니다.

  조합

조합에 대해 모르는 사람은 없을 것이라고 생각하지만

혹시나 조합에 대해 모르는 사람이 있을 수도 있다고 생각하기에

간단한 설명을 드리겠습니다.

조합은 영어로 Combination이라고 하며 기본적인 원리는 이렇습니다.

n개에서 r개를 고를 수 있는 경우의 수입니다.(중복 X)

예를 들어 보겠습니다.

A / B / C / D / E 라는 사람 중에 2명 씩 짝을 이룰수 있는 경우를 구해보겠습니다.

AB / AC / AD / AE / BC / BD / BE / CD / CE / DE 이렇게 경우의 수를 구할 수 있습니다.

여기서 n = 5 가 되겠고 r = 2 가 됩니다.

그래서 조합에서는 이러한 표현을 5C2 이렇게 표현을 하며 

이를 일반화 하게 되면  이렇게 됩니다.

이것을 이용하여 문제를 해결해보겠습니다.

  문제

  풀이

일단 이전에 이항계수를 풀 때와 비슷하게 풀었습니다.

단, 범위가 100까지 이기 때문에 n! 을 했을 경우 어마어마하게 숫자가 커집니다.

그래서 int와 long도 부족합니다.

그래서 BigInteger를 사용하여 문제를 풀었습니다.

BigInteger는 많이 사용을 안해봐서 어색했는데 어찌 풀었습니다.

또한 재귀함수로 풀면 범위가 넓어 당연히 시간이 초과되었습니다.

  코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Scanner;
 
public class Beak2407 {
 
    static BigInteger[][] list;
 
    public static void main(String[] args) throws IOException {
 
        Scanner sc = new Scanner(System.in);
        BigInteger big = new BigInteger("1");
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        list = new BigInteger[1001][1001];
        list[1][0] = list[1][1] = big;
        
        for(int i=2;i<=n;i++) {
            for(int j=0;j<=i;j++) {
                if(i == j || j == 0)
                    list[i][j] = big;
                else
                    list[i][j] = list[i-1][j-1].add(list[i-1][j]);
            }
        }
    
        System.out.println(list[n][m]);
    }
}