[BOJ/백준][Silver2] 2004 : 조합 0의 개수 (Kotlin))

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

2004번: 조합 0의 개수

 

[난이도] Silver2
[유형] 수학

[풀이]
nCm 은 n!/(m!x(n-m)!) 로 표현된다.

문제 https://www.acmicpc.net/problem/1676 에서 봤듯이 끝의 0의 개수는 어떤 수를 소인수분해 했을 때 5x2가 몇개나 있는지에 따라 결정된다.
n!/(m!x(n-m)!) 식에서 2와 5가 최종적으로 몇개 남는지를 구하고 둘중 최솟값을 출력하면 된다.

 

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min
fun get(p:Int,k:Int):Int{
    var cnt=0
    var n=p
    while(n>0){
        n/=k
        cnt+=n
    }
    return cnt
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val ip=readLine().split(' ')
    val N=ip[0].toInt()
    val M=ip[1].toInt()
    val a = get(N,2)-get(N-M,2)-get(M,2)
    val b = get(N,5)-get(N-M,5)-get(M,5)
    println(min(a,b))
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/2004.cpp