[백준] 1676 (팩토리얼 0의 개수)

#1 알고리즘

#1-1 문제의 핵심

이 문제의 핵심은, x!가 가지고 있는 2*5 쌍의 갯수만큼 뒤에 0이 붙는다는 규칙의 파악이다.

 

#1-2 상향식 동적 프로그래밍

동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근

상향식 동적 프로그래밍을 구현해 풀었다.

 

 

#2 코드 - 코틀린

val twoCounts = Array(501) {0}
val fiveCounts = Array(501) {0}

// 2*5 쌍의 갯수를 구하는 문제
fun main() {
    for(i: Int in 1..500) {
        twoCounts[i] = twoCounts[i-1] + calculateFactorCount(i, 2)
        fiveCounts[i] = fiveCounts[i-1] + calculateFactorCount(i, 5)
    }

    val n = readln().toInt()
    println(minOf(twoCounts[n], fiveCounts[n]))
}

fun calculateFactorCount(number: Int, factor: Int): Int {
    var n = number.toDouble()

    var count = 0
    while(n >= factor && (n / factor).toInt() * factor == n.toInt()) {
        n /= factor
        count++
    }
    return count
}