백준 1676번 C++ 풀이

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

1676번: 팩토리얼 0의 개수

시간 제한	메모리 제한	solved.ac 티업
2초	128MB	실버 4

문제

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

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

---

단순히 팩토리얼을 계산하는 문제가 아니라, 처음 0이 아닌 숫자가 나올 떄까지의 0의 개수를 구하는 것이다. 팩토리얼은 숫자가 조금만 커져도 그 값이 엄청나게 커지기 때문에, 단순 계산으로 시도하면 당연히 오버플로우가 나게 된다.

 

문제에 조금 집중해보면, 처음 0이 아닌 숫자가 나올때까지의 0은, 10의 거듭제곱꼴이 곱해져 있다는 뜻이다. 10은 2 x 5로 분해되기 때문에, 결국 이 문제는 주어진 팩토리얼을 소인수 분해했을 때, 2와 5가 몇개가 있는지를 찾아야 하는 문제이다.

 

또한, 2와 5의 개수가 다를 수도 있는데, 그 개수가 더 적은 쪽이 당연히 답일 것이다. 2^3 * 5^2라는 숫자가 있다면, 이 숫자는 10^2 * 2이기 때문이다.

 

2부터 입력받은 숫자까지 반복문을 돌면서 소인수 2와 5의 개수를 세서 더 적은쪽을 출력하면 된다.

 

#include <bits/stdc++.h>
using namespace std;

void solution(int n) {
    int cnt_2 = 0;
    int cnt_5 = 0;
    int temp;
    for(int i = 2; i <= n; i++) {
        temp = i;
        while(temp % 2 == 0) {
            cnt_2++;
            temp /= 2;
        }
        while(temp % 5 == 0) {
            cnt_5++;
            temp /= 5;
        }
    }
    cout << min(cnt_2, cnt_5);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    solution(n);
}