[알고리즘] 백준 2407 - 조합

분류 : DP

1. 문제

https://www.acmicpc.net/problem/2407
nCm을 출력한다.

2. 입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

3. 풀이

1) 사칙연산

사실 원래 DP로 푸는 문제인데 그냥 연산으로 해도 풀려서 그렇게 풀었다.

nCm = n! / (n-m)!m!
= n x (n-1) x ... x (n-m+1) / m!

이라는 것을 이용해

• 분자 : n부터 n-m+1까지 곱함
• 분모 : 1부터 m까지 곱함

을 수행하고 분자/분모로 나누어 값을 구해주었다.

*주의점 : int나 long으로 하면 결과값의 범위를 다 담지 못하기 때문에 BigInteger로 선언해야 한다.

2) DP

추후 추가

4. 코드

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 solution() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        //integer로 담기에는 범위가 너무 커서 BigInteger로
        BigInteger n1 = BigInteger.ONE;
        BigInteger n2 = BigInteger.ONE;

        for(int i=0;i<m;i++){
            //분자
            n1 = n1.multiply(new BigInteger(String.valueOf(n-i)));
            //분모
            n2 = n2.multiply(new BigInteger(String.valueOf(i+1)));
        }

        BigInteger answer = n1.divide(n2);

        System.out.println(answer);
    }
}