조합 0의 개수

오랜만에 알고리즘 풀이를 올려본다.

많이 어려운 문제는 아니지만 중간고사 + 중간 기말 대체 과제 앱만들기 + 면접 준비로 한동안 알고리즘 공부를 쉬었더니 마냥 쉽게 풀리진 않았다.

풀이

우선 조합에 대한 어느정도 사전 지식이 있어야 한다.

nCm = n!/ ( (n-m)! * m! ) 으로 표현할 수 있다.

예를 들어 10C3의 경우 (10 * 9 * 8) / (3 * 2 * 1) = (10 * 9 * .. * 1) / { (7 * 6 * .. * 1) * (3 * 2 * 1) } 로 표현된다.

그리고 임의의 수 N에 대하여 끝에서 부터 0의 갯수, 즉, 10을 인수로 몇개 갖는지는 N의 소인수분해 후 인수 2와 5 중 최솟값 이 된다.

10을 만들기 위해서는 무조건 2와 5를 곱해줘야 하므로 소인수분해 후 2와 5가 나온 갯수 중 작은 값이 10이 나오는 갯수가 된다.

분자의 수에서 0의 갯수를 그렇게 찾았다면 분모로 나누는 수에서 나오는 0의 갯수를 분모 값에서 빼주면 분수의 0 갯수를 알 수 있다.

코드

// 2022-05-03
// https://www.acmicpc.net/problem/2004

class Solution{
    fun solution(n:Int, M:Int):Int{
        var m = if(M*2>n) M else n-M
        return minOf(fac(n,2)-fac(n-m,2)-fac(m,2),fac(n,5)-fac(n-m,5)- fac(m,5))
    }

    fun fac(factorial:Int, divider:Int):Int{
        var n = factorial
        var value = 0
        while( n > 0){
            n/=divider
            value+=n
        }
        return value
    }
}

fun main() {
    val str = readLine()!!.split(' ')
    println(Solution().solution(str[0].toInt(), str[1].toInt()))
}