백준 11687 팩토리얼 0의 개수 Kotlin (수학)

문제 출처 : https://www.acmicpc.net/problem/11687

11687번: 팩토리얼 0의 개수

문제

가장 끝의 0의 개수가 M개인 N! 중에서 가장 작은 N을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다.

출력

$

가장 끝의 0의 개수가 M개인 N! 중에서 가장 작은 N을 출력한다. 그러한 N이 없는 경우에는 -1을 출력한다.

알고리즘 분류

• 수학
• 정수론
• 이분 탐색

풀이

2022.07.19 - [알고리즘 문제 풀이/백준] - 백준 팩토리얼 0의 개수 Kotlin (1676)

0의 개수를 구하는 방법은 이전 문제와 동일하다.

이 문제는 입력의 크기가 크기 때문에 이전 문제와 동일한 코드로는 통과할 수 없다.

우선 입력으로 주어지는 M은 N!의 0의 개수이다.

0의 개수가 M과 같은 N!중 최소가 N의 최솟값을 찾아야 하는데,

M이 최대 1억이기 때문에 N은 M보다 충분히 크게 잡아야 한다.

따라서 N의 범위는 1부터 넉넉히 987,654,321로 잡을 수 있는데,

이 범위 내에서 M과 같은 N의 최솟값을 이분 탐색으로 찾으면 된다.

n이 mid일 때 0의 개수가 m보다 크거나 같으면 이분 탐색에서 왼쪽을 탐색하여 mid를 줄이고

n이 mid일 때 0의 개수가 m과 같으면 정답을 갱신,

n이 mid일 때 0의 개수가 m보다 작으면 이분 탐색에서 오른쪽을 탐색하여 mid를 늘린다.

 

코드

val br = System.`in`.bufferedReader()
fun getInt() = br.readLine().toInt()

fun countZero(mid: Int) : Long {
    var key: Long = 5
    var sum: Long = 0
    while (key <= mid) {
        sum += mid / key
        key *= 5
    }
    return sum
}
fun main() = with(System.out.bufferedWriter()) {
    val m = getInt().toLong()
    var s = 1
    var e = 987_654_321
    var answer = 0
    while(s<=e){
        val mid = (s+e)/2
        val cnt = countZero(mid)
        if(cnt >= m){
            if(cnt == m) answer = mid
            e = mid - 1
        }
        else{
            s = mid + 1
        }
    }
    write("${if(answer==0) -1 else answer}")
    close()
}