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

문제

---

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

생각하기

---

• 500! 팩토리얼값은 상상할 수 없을 만큼 큰 수 이므로 혹시 계산하게 된다면 Long이 아닌, BigInteger를 써야한다.

• 이 문제를 정석으로 푼다면 시간초과가 발생하기 때문에 규칙을 찾아야 한다.

동작

    while(N >= 5) {
        count += N / 5
        N /= 5
    }

팩토리얼에서 0의 개수는 5! 단위로 0의 개수가 한개씩 증가하는 패턴이 있다.

따라서 5로 나눠서 count를 1씩 증가하면 값을 구할 수 잇다.

코드

---

Java

Kotlin

import java.io.*

fun main() {
    val br = BufferedReader( InputStreamReader(System.`in`) )

    var N = br.readLine().toInt()
    var count = 0

    while(N >= 5) {
        count += N / 5
        N /= 5
    }
    print(count)
} // End of main