백준 11687번
https://www.acmicpc.net/problem/11687

문제

---

생각하기

---

• 이분 탐색 문제이다.

  • 재귀를 통해서 구현하였다.

• 탐색 범위가 넓기 때문에 이분 탐색을 통해서 N을 찾아야 한다.

• 이 문제의 핵심은 이분 탐색도 될 수 있지만, 사실 '0의 개수를 어떻게 효율적으로 빠르게 찾는가' 가 이 문제의 핵심이다.

  • N!의 0의 개수 -> 1 ~ N! 5의 배수의 개수 -> 소인수 5의 배수의 개수

동작

코드

---

Kotlin

import java.io.*

// input
private lateinit var br: BufferedReader

// variables
private var M = 0
private var ans: Long = Long.MAX_VALUE

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    val sb = StringBuilder()

    // input
    input()

    // binarySearch
    binarySearch(1, (M * 5).toLong())

    if (ans == Long.MAX_VALUE)
        sb.append(-1)
    else {
        sb.append(ans)
    }

    bw.write(sb.toString())
    bw.close()
} // End of main

private fun binarySearch(low: Long, high: Long): Long {
    if (low > high) {
        return -1L
    }

    val mid = (low + high) / 2
    val result = check(mid)

    if (result >= M) {
        // 기존의 정답 보다 새로운 mid의 값이 더 클 때, (mid를 낮춰야 할 때)
        if(result.toInt() == M) {
            ans = Math.min(ans, mid)
        }

        val temp = binarySearch(low, mid - 1)
        return if (temp == -1L) {
            mid
        } else {
            temp
        }
    } else {
        return binarySearch(mid + 1, high)
    }
} // End of binarySearch

// 0의 개수를 확인하는 함수
private fun check(mid: Long): Long {
    var zeroCount = 0L
    var tempMid = mid

    while (tempMid >= 5) {
        zeroCount += (tempMid / 5)
        tempMid /= 5
    }
    return zeroCount
} // End of check

private fun input() {
    M = br.readLine().toInt()
} // End of input