[BJ]17213. 과일서리

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

17213번: 과일 서리

 

 

접근 하기

 

중복조합

N개의 과일에서 중복을 허용해서 M개를 고르는 문제이다. 선택된 M개의 과일에는 순서가 없기 때문에 조합이 적용된다.

단 모든 과일은 한번씩은 선택되어야 한다. 그렇다면 애초에 이 과일들은 한번씩 선택한 것으로 간주하고 나머지 N개의 과일에서 M-N개를 중복해서 고르는 중복 조합(nHr)으로 처리하면 된다.

 

중복조합의 개수?

그럼 중복조합의 개수는 어떻게 구할 것인가? 중복조합은 코드적으로 많이 작성해봤지만 개수만 딸랑 구해본적은 거의 없는것 같다. 물론 중복조합을 구하기 위해서는 다음의 아름다운 공식이 있다.

 

nHr=n+r−1Cr

공식을 기억하고 있다면 정말 좋겠지만 공식의 맹점은 떠오르지 않으면 말짱 꽝이라는 점. 

그래서 위 공식을 간단히 유도해보는 시간을 가져보자.

 

{1, 2, 3, 4}의 4가지 요소에서 2개를 중복해서 뽑는 조합을 구해보면 다음의 10가지가 나온다.

[1,1], [1,2], [1,3], [1,4], [2,2], [2,3], [2,4], [3,3], [3,4], [4,4]

 

도대체 10이라는 가지수를 어떻게 구할 것인가? 중복 조합은 어렵지만 조합은 쉽다!!

먼저 위 조합 구성의 두 번째 요소들에 1을 더해줘보자. 그럼 아래처럼 바뀐다.

[1,2], [1,3], [1,4], [1,5], [2,3], [2,4], [2,5], [3,4], [3,5], [4,5]

 

그럼 이 결과는.. 놀랍게도 {1, 2, 3, 4, 5} 에서 중복되지 않게 2개를 뽑아서 나열한 조합이 된다. 즉 4H2 = 5C2이다.

 

 

만약 {1, 2}에서 중복을 허용해서 3개를 뽑는다고 가정해보자.

[1, 1, 1], [1, 1, 2], [1, 2, 2], [2, 2, 2] 의 4가지 경우가 발생한다. 이 내용을 위와 같이 중복되지 않는 형태로 만들려면 2번째에는 1, 세번째에는 2를 각각 더해보면 된다.

[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]

결과는 역시 놀랍게도 {1, ,2, 3, 4}에서 중복되지 않게 3개를 뽑아 나열하는 조합이 된다. 즉 2H3 = 4C3이다.

 

이 과정을 일반화 해보면 위의 공식이 된다.

 

 

 

주의사항

이 문제에서는 N=10, M=30 까지이므로 39!의 값이 필요하다. 연산의 회수는 몇번 안되지만 값의 크기는 정수를 벗어나기 때문에 BigInteger 클래스를 이용해서 연산해주어야 한다.

 

코드 구현

 

Java

public class BJ_S2_17213_과일서리 {

    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static StringTokenizer tokens;

    static int N, M;
    static BigInteger[] factorial;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(instr));
        N = Integer.parseInt(input.readLine());
        M = Integer.parseInt(input.readLine());
        makeFactorial();
        System.out.println(factorial[M - 1].divide(factorial[M - N])
                                           .divide(factorial[N - 1]));
    }

    public static void makeFactorial() {
        factorial = new BigInteger[40];
        factorial[0] = new BigInteger("1");
        for (int i = 1; i < factorial.length; i++) {
            factorial[i] = factorial[i - 1].multiply(new BigInteger(i + ""));
        }
    }

    public static String instr = "3\n"
                                 + "10";
}

 

 

관련 링크