[백준] 2407 : 조합 (JAVA/자바)

문제

BOJ 2407 : 조합 - https://www.acmicpc.net/problem/2407

풀이

단순의 조합의 개수를 구하는 문제이지만, n의 범위가 최대 100이기 때문에 100!을 하게 되면 숫자가 아주아주 커지게 된다. int로는 택도 없고, long으로도 힘들다. BigInteger라는 자료형을 사용해야 한다.

조합을 구하는 공식인 nCr = n! / (n-r)! * r! 을 그대로 코드에 적용해서 분모, 분자의 값을 각각 구해준 뒤 나눠주면 결과값이 된다.

코드

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");

        int n = Integer.parseInt(inputs[0]);
        int m = Integer.parseInt(inputs[1]);

        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);
    }
}

정리

✔ 알고리즘 분류 - 그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색
✔ 난이도 - ⚪ Silver 2

🤦‍♀️ 오늘의 메모

• 주어진 조건의 최대 범위를 잘 보고 자료형을 선택하기!
  • int : -2,147,483,648 ~ 2,147,483,647
  • long : -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
  • BigInteger : 문자열 형태로 이루어져 있어 숫자의 범위가 무한

참고 사이트

https://wellohorld.tistory.com/109