백준 11687번
https://www.acmicpc.net/problem/11687
이분 탐색 문제이다.
탐색 범위가 넓기 때문에 이분 탐색을 통해서 N
을 찾아야 한다.
이 문제의 핵심은 이분 탐색도 될 수 있지만, 사실 '0의 개수를 어떻게 효율적으로 빠르게 찾는가' 가 이 문제의 핵심이다.
N
!의 0의 개수 -> 1 ~ N
! 5의 배수의 개수 -> 소인수 5의 배수의 개수
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