[백준 1010번] [Kotlin] 다리 놓기

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

1010번: 다리 놓기

 

난이도 : 실버 5
태그 : 수학, 다이나믹 프로그래밍, 조합론

 

 

설명

서쪽과 동쪽의 다리를 서로 잇는 문제입니다.

항상 양쪽 다리 개수가 같거나, 강 동쪽이 다리가 더 많으므로,

단순히 오른쪽 다리 m개 중 왼쪽다리 개수 n만큼을 고르는 조합으로 볼 수 있습니다.

즉, mCn 으로 볼 수 있겠네요.

 

 

 

소스코드

fun main() = with(System.`in`.bufferedReader()) {
    val sb = StringBuilder()
    repeat(readLine().toInt()) {
        val (n, m) = readLine().split(" ").map { it.toInt() }

        var result = 1L

        for (i in 1 .. n) result = result * (m - i + 1) / i

        sb.append(result).append("\n")
    }
    print(sb)
}