[Kotlin] 백준 12785 : 토쟁이의 등굣길

문제 링크

12785번: 토쟁이의 등굣길

---

---

문제 해설

최단 경로 문제다. 토쟁이의 집부터 토스트 가게까지의 최단경로와 토스트 가게부터 학교까지의 최단경로를 구하여 두 값을 곱한 결과를 1,000,007로 나눈 나머지를 출력하면 된다.

 

최단 경로 문제는 조합으로 해결할 수 있다.

위와 같은 모양의 지도가 있을 때 start에서 end까지 이동하는 최단 경로의 수는 →오른쪽 5개와 ↑위쪽 3개로 이루어진 집합에서 5개의 →오른쪽이나 3개의 ↑위쪽을 뽑는 경우의 수가 된다. 따라서 위와 같은 경우에서 start에서 end까지 이동하는 최단 경로의 수는 \( _{8}\mathrm{C}_{3} = _{8}\mathrm{C}_{5}\)가 된다.

 

다시 문제로 돌아와서 토쟁이의 집에서 토스트 가게까지의 거리는 \(_{(x-1 + y-1)}\mathrm{C}_{(y-1)}\)이 된다(토쟁이의 집 위치가 (0, 0)이 아니라 (1, 1)이기 때문). 그리고 토스트 가게부터 학교까지의 거리는 \(_{(w-x+h-y)}\mathrm{C}_{(h-y)}\)가 된다. 이 두 값을 1,000,007로 나눈 나머지를 곱한 결과를 1,000,007로 나눈 나머지가 정답이 된다.

 

단, 계산할 때 \(23!\)만 되더라도 ULong의 범위를 아득히 초과하여 오버플로가 발생하기 때문에 BigInteger로 계산해야한다. 

---

Code

fun main() = with(System.`in`.bufferedReader()) {
    val (w, h) = readLine().split(' ').map { it.toInt() - 1 }	// 시작점이 (1, 1)이므로 1씩 빼줌
    val (x, y) = readLine().split(' ').map { it.toInt() - 1 }	// 시작점이 (1, 1)이므로 1씩 빼줌
    val toToast = comb(x + y, y)
    val toastToSchool = comb(w - x + h - y, h - y)
    println((toToast * toastToSchool) % 1000007)
}

fun comb(n: Int, k: Int): Long {
    var a = n
    val b = minOf(k, n - k)
    var result = 1.toBigInteger()
    var kFac = 1.toBigInteger()
    repeat(b) {
        result = result.multiply(a--.toBigInteger())
    }
    for (i in 2..b) {
        kFac = kFac.multiply(i.toBigInteger())
    }
    return result.divide(kFac).mod(1000007.toBigInteger()).toLong()
}