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

[백준 알고리즘]

팩토리얼 문제에 이어서 팩토리얼에 관련된 문제를 하나 더 풀어보았습니다.

  문제

  해석

일단 이것을 어떻게 풀 것인가 생각을 해보았습니다. 

너무 깊게 생각하다가 자꾸 이상하게 풀어서 쉽게 보자 생각했습니다.

그래서 다시 한번 보니까 문제는 생각보다 간단했습니다.

일단 한번 문제를 봅시다. 

N! 까지 뒤에서 부터 0이 아닌 숫자가 나올 때 까지 0의 갯수를 구하는 것 입니다.

그렇다면 0이 나오려면 어떻게 해야할까요? 

10이 나온다면 0이 나오게됩니다. 00이 나오려면 10*10이 되면 됩니다.

다시 말하면 10이 몇 번 곱해지는지에 따라 0의 갯수가 정해집니다.

예를 들어봅시다.

5! = 1 x 2 x 3 x 5 = 30 (0이 1번)

6! = 1 x 2 x 3 x 5 x 6 = 180 (0이 1번)

3! = 1 x 2 x 3 = 6 (0이 0번) 

10이 만들어지기 위해선 2 와 5가 필요합니다. 

이 말을 바꿔보자면 2 와 5의 개수에 따라 0이 결정된다는 것입니다.

10! 를 예를 들어봅시다. 2와 5를 따로 묶어보겠습니다.

1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 = (2^8) x (5^2) x (3^4) x 7 이렇게 됩니다.

따로 묶었고 이제 10으로 다시 묶어보면 (10^2) x (2^6) x (3^4) x 7 이됩니다.

그렇다면 10을 입력하면 0의 갯수는 2가 됩니다.

여기서 2와 5 중에 작은 값이 0의 갯수가 됩니다.

이해가 되시겠죠? 

  코드

import java.util.Scanner;
 
public class Beak1676 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
        int result = 1;
        int countT = 0, countF = 0;
        for (int i = 1; i <= n; i++) {
            result = i;
 
            while (result % 2 == 0 || result % 5 == 0) {
                if (result % 2 == 0) {
                    result /= 2;
                    countT++;
                }
                if (result % 5 == 0) {
                    result /= 5;
                    countF++;
                }
            }
        }
        if(countT < countF)
            System.out.println(countT);
        else
            System.out.println(countF);
    }
}