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

 

N!을 계산한 후에 문자열로 변환하고 charAt() 써서 0의 개수를 세면 되는거아냐?!

(어림도 없음)

 

 

이러한 방식은 N이 조금만 커져도 int나 long으로 표현할 수 없을 정도로 큰 수가 되기 때문에

수학적으로 접근하는 것이 훨씬 간결하고 효율적이다.

N!을 계산하지 않고도 0의 개수를 알 수 있다.

 

 

이 문제에서는

팩토리얼의 끝에 있는 0의 개수는 5의 배수 개수에 의해 결정된다

는 점을 활용하면 된다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int count = 0;
        for(int i=5; i<=N; i*=5) {
            count += N / i;
        }

        System.out.println(count);
    }
}

 

 

 

---

 

 

 

프로그래밍 문제를 해결할 때는 단순히 직관에만 의존하기보다

수학적 규칙이나 공식을 이용해서 효율적으로 접근할 수 있는지를 고려해보자!