[BaekJoon] 2407 조합

1.  문제 링크

2.  문제

요약

• n과 m이 주어질 때, nCm 조합의 값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 n과 m이 주어지고 각 n,m은 5보다 크거나 같고 100보다 작거나 같은 값입니다.
• 출력: nCm의 값을 출력합니다.

3.  소스코드

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


public class Main {
	public BigInteger getCombination(int n, int m) {
		BigInteger num1 = BigInteger.ONE; // 1
		BigInteger num2 = BigInteger.ONE; // 1
		for(int i = 0; i < m; i++) {
			num1 = num1.multiply(new BigInteger(String.valueOf(n - i))); // BigInteger의 곱셈
			num2 = num2.multiply(new BigInteger(String.valueOf(i + 1))); // BigInteger의 곱셈
		}
		BigInteger result = num1.divide(num2); // BigInteger의 나눗셈
		return result;
	}
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input = br.readLine();
        br.close();
        StringTokenizer st = new StringTokenizer(input);
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Main main = new Main();
        bw.write(main.getCombination(n, m) + "\n");
        bw.flush();
        bw.close();
    }
}

4.  접근

• 조합을 구하는 과정에서 여러 수의 곱셈이 이루어지는데 이 값의 범위가 Integer의 범위를 넘어서기 때문에 Integer를 이용하여 조합의 값을 구할 수 없습니다.
• 그렇기 때문에 문자열 형태로 이루어져 숫자 범위가 무한한 BigInteger를 이용하여 조합의 값을 구합니다.
• nCr = n! / (n-r)!r!
• 위 공식을 이용하여 분자와 분모를 계산합니다. 위 코드에서 이를 계산할 때는 (n-r)!에 대해서 분자와 분모를 약분해 준 후에 분자와 분모에 대한 계산을 진행하였습니다.
• BigInteger.multiply(BigInteger)를 이용하여 BigInteger의 곱셈을 진행할 수 있고 BigInteger를 초기화할 때는 인자값으로 String을 넘겨줘야 하기 때문에 곱하려는 값을 String으로 변경하여 BigInteger의 인자값으로 넘겨줍니다.
• 분자와 분모를 곱셈을 통하여 값을 구했다면 BigInteger.divide(BigInteger)를 이용하여 분자와 분모의 나눗셈을 진행하고 이 값을 출력합니다.