[백준/BOJ] 651번: 이항 쇼다운

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

6591번: 이항 쇼다운

문제

n개의 원소 중에서 k개를 순서 없이 선택하는 방법의 수는 몇 가지 일까?

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 231-1 을 넘지 않는 두 자연수 n(n ≥ 1)과 k(0 ≤ k ≤n)로 이루어져 있다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 정답을 출력한다. 항상 정답이 231보다 작은 경우만 입력으로 주어진다.

해설

재귀를 통한 DFS를 이용하여 문제를 풀었었다.

이 방법은 n, k의 범위가 2³¹-1이어서 재귀를 너무 많이 돌아 스택오버플로우가 나게 된다.

 

다음은 수학에서 푸는 조합 공식을 이용하였다.

조합 공식을 보면 _nC_k = _nC_n-k이다. 

따라서 우선 k와 n - k 중 더 작은 값을 구하여 temp라 하자

 

이제 temp만큼 반복을 하며 n--를 곱하고, 1부터 temp까지를 나눠주면 된다.

단 범위가 큰 만큼 답을 저장할 변수는 Long형으로 선언하여야 한다.

소스 코드

fun main() = with(System.`in`.bufferedReader()) {
    while(true) {
        var (n, k) = readLine().split(" ").map { it.toInt() }
        if(n == 0 && k == 0) break
        var div = 1
        var ans = 1L
        if(n - k < k) k = n - k
        while(k-- >  0) {
            ans *= n--
            ans /= div++
        }
        println(ans)
    }
}