BOJ) 조합 (2407 번)

조합

2407번: 조합

 

수학의 조합(Combination)을 구현하는 문제다.

조합 자체는 여러 방법으로 구할 수 있지만, 반복문을 통해 풀기로 했다.

그래서 combination을 직접 몇 개 써보면서 규칙을 찾았다.

 

nCm => n! / ((n - m)! * m!) 이라는 공식이 있는데, 이를 약분하면

nCm => (n*n-1*... *n-m+1) / (m*m-1*...*1) 라는 식이 나온다.

 

n =10인 경우를 살펴보자

N	M	식	값
10	0	10! / ( (10 -0)! * 0! ) => 10! / 10!	1
10	1	10! / ( (10-1)! * 1! ) => 10! / 9! => 10 / 1	10
10	2	10! / ( (10-2)! * 2! ) => 10! / 8! /2! => 10*9 / ( 2*1 )	45
10	3	10! / ( (10-3)! * 3! ) => 10! / 7! /3! => 10*9*7 / ( 3*2*1 )	120

 

위의 분자와 분모를 잘 살펴보면 규칙적으로 곱하고 나눠준다. 이를 식으로 표현하면,

 

n C m = n C m-1 * (n - m +1 ) / m

위와 같은 식이 나온다.

 

또한, 불필요한 계산을 줄이기 위해서 Combination의 특징을 이용했다.

n C m = n C n-m 이라는 특징을 이용해서 조합의 절반만 계산하고, 절반 이후는 이전과 대칭해서 값을 대입해주었다.

 

처음에 아무 생각 없이 값이 크니까 long으로 해야지~ 하고 long type으로 설정했다가 틀렸었다.

하지만 최대의 조합인 100 C 50의 경우 long의 범위도 넘어가서 BigInteger를 사용해야했다.

BigInteger에 관련된 주요 내용은 Oracle의 공식 문서

를 참고하자.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Combination_2407 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
    br.close();
    solution(n,m);
  }

  private static void solution(int n, int m) {
    BigInteger[] combination = initCombination(n);
    int mid = n/2;
    int standard = n % 2 ==0 ? mid : mid+1;
    for(int i=1; i<=mid; i++) {
      combination[i] = combination[i-1].multiply(BigInteger.valueOf((n-i+1))).divide(BigInteger.valueOf(i));
    }
    for(int i=1; i<=mid; i++) {
      combination[mid+i] = combination[standard-i];
    }

    System.out.println(combination[m]);
  }

  private static BigInteger[] initCombination(int n) {
    BigInteger[] combination = new BigInteger [n+1];
    combination[0] = new BigInteger("1");

    return combination;
  }
}