[Kotlin] 백준 1010 : 다리 놓기

문제 링크

1010번: 다리 놓기

---

 

---

문제 해설

문제의 결론만 따지자면 \( _{m}\mathrm{C}_{n}\)을 구하는 문제다. 강 서쪽의 n개의 사이트를 모두 선택하여 강 동쪽의 임의의 m개의 사이트에 하나씩 연결해야한다. n ≤ m이므로 m개 중 n개를 선택하는 경우의 수와 같다는 것을 알 수 있다. 여기서 다리가 겹쳐질 수 없다는 조건이 있는데 이에 대한 예시는 다음 그림과 같은 두 경우를 들어보겠다.

 

각 경우를 배열로 나타내면 첫번째는 [1, 2, 3], 두번째는 [2, 3, 1]이 된다. 그런데 다리가 겹쳐질 수 없기 때문에 [2, 3, 1]은 무효한 경우가 된다. [2, 1, 3]이나 [1, 3, 2]의 경우도 마찬가지로 다리가 겹치게 되므로 무효가 된다. 즉 동쪽 사이트에서 1, 2, 3번 사이트가 선택되는 경우는 [1, 2, 3]밖에 존재하지 않으며, 이는 순서에 상관없이 뽑는 조합(Combination)이 된다.

 

정답은 조합의 개수만 구하면 되기 때문에 \( _{m}\mathrm{C}_{n} = \frac{_{m}\mathrm{P}_{n}} {n!} \)를 간단한 반복문으로 계산을 했다. 

---

Code

import java.math.BigInteger

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    val times = readLine().toInt()
    repeat(times) {
        bw.write("${readLine().split(" ").map { it.toInt() }.let { comb(it[1], it[0]) }}\n")
    }
    bw.close()
}

fun comb(n: Int, k: Int): BigInteger {
    var a = n
    val b = minOf(k, n - k)
    var result = 1.toBigInteger()
    var kFac = 1L
    // nPk
    repeat(b) {
        result = result.multiply(a--.toBigInteger())
    }
    // k!
    for (i in 2..b) {
        kFac *= i
    }
    // nPk / k!을 반환
    return result.divide(kFac.toBigInteger())
}