백준 2407번 조합 JAVA

링크텍스트

설명

n개의 숫자에서 r개를 뽑는 경우의 수
처음에는 long을 사용해서 풀었는데 long 최대값: 9,223,372,036,854,775,807
20! ≈ 2.43 × 10¹⁸ (마지막으로 안전)
21!부터 바로 터진다. 그래서 BigInteger 사용헀다.
시간복잡도: O(n(nlogn)²), 공간복잡도: O(nlogn)

회독

• [ x ] 1회
• 2회
• 3회

코드

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long n = Long.parseLong(st.nextToken());
        long m = Long.parseLong(st.nextToken());

        BigInteger fn = factorial(n);
        BigInteger fm = factorial(m);
        BigInteger nm = factorial(n-m);

        System.out.println(fn.divide(fm.multiply(nm)));
        
    }

    public static BigInteger factorial(long num){
        BigInteger sum = BigInteger.ONE;
        for(long i=2;i<=num;i++){
            sum = sum.multiply(BigInteger.valueOf(i));
        }

        return sum;
    }
}