백준 - 1676 - 팩토리얼 0의 개수

https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

[실패한 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B_1676 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int num = fact(N);

        String A = String.valueOf(num);
        String B = String.valueOf(solution(num));

        String count = String.valueOf(A.length()-B.length());

        System.out.println(count);
    }

    static int fact(int n){
        if(n <= 1){
            return n;
        }
        else {
            return fact(n-1)*n;
        }
    }

    public static int solution(int n){

        int result = 0;
        while (n != 0){
            result = result * 10 + n % 10;
            n /= 10;
        }
        return result;
    }
}

 

....ㅠㅡㅠ

 

 

뒷자리에 0이 나오는 경우는 2와 5가 곱해져 있을 때다.

소인수분해를 해서 2와 5가 존재할 경우 뒷자리는 0으로 끝난다.

 

뒷자리가 0이 n개 있다는 의미는 2와 5가 n개씩 짝지어 존재한다는 것이다.

 

팩토리얼 값을 보면 2는 3개, 5는 2개 있다.

2와 5를 짝지을 수 있는 개수는 2개이며, 뒷자리 수 0개의 개수와 같다.

 

팩토리얼 값을 보면 2는 5보다 작은 수여서 연속된 수를 곱하게 되면 자연스럽게 모든 값들의 소인수 분해들은 2의 개수가 5의 개수보다 많다.

 

기본적으로 5의 개수에 따라 값이 변화한다고 보면 된다. 그리고 5의 n승에 따라 카운트 값을 한 개 더 추가해 주면 된다.

즉, 단순히 5로 나누는 것이 아니라 반복문을 통해 5로 나누면서 누적합을 구해줘야 한다. 

 

 

[정답 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B_1676 {
    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;

        while (N >= 5){
            count += N / 5;
            N /= 5;
        }
        System.out.println(count);
    }
}

 

 

 

 

 

참고 블로그 : https://st-lab.tistory.com/165