[백준/BOJ] 2407: 조합

https://www.acmicpc.net/problem/2407

2407번: 조합

문제

_nC_m을 출력한다.

해설

_nC_m을 구하는 공식은 다음과 같다.

N!, M!, (N-M)! 이 세 개를 구하면 문제를 풀 수 있다.

 

이 문제에서의 범위는 n, m이 100까지 가능하다.

따라서 어느 값 이후부터는 아주 큰 값이 되어 int와 long의 범위를 벗어난다.

 

이를 해결하기 위해 BigInteger 자료형을 사용해야 한다.

BigInteger는 무한한 수를 오차없이 출력할 수 있다.

소스 코드

import java.math.BigInteger

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toBigInteger() }
    val n1 = multi(n)
    val n2 = multi(m)
    val n3 = multi(n - m)
    println(n1 / (n2 * n3))
}

fun multi(n: BigInteger): BigInteger {
    return if(n <= BigInteger.ONE) BigInteger.ONE
    else n * multi(n.subtract(BigInteger.ONE))
}