[백준]#2407 조합

SeungBird·2020년 8월 28일
0

⌨알고리즘(백준)

목록 보기
116/401

문제

nCm을 출력한다.

입력

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

출력

nCm을 출력한다.

예제 입력 1

100 6

예제 출력 1

1192052400

풀이

이 문제는 간단한 조합 문제이지만 BigInteger 같이 큰 수를 저장할 수 있는 변수가 필요하다.

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

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int r = Integer.parseInt(input[1]);

        System.out.println(perm(n, r));
    }

    static BigInteger top(int n, int r) {
        BigInteger res = BigInteger.ONE;

        for(int i=0; i<r; i++) {
            res = res.multiply(BigInteger.valueOf(n));
            n--;
        }
        return res;
    }

    static BigInteger perm(int n, int r) {
        if(r>50)
            r=n-r;

        return top(n, r).divide(factorial(r));
    }


    static BigInteger factorial(int x) {
        if(x==0)
            return BigInteger.valueOf(1);

        else
            return BigInteger.valueOf(x).multiply(factorial(x-1));
    }
}
profile
👶🏻Jr. Programmer

0개의 댓글