[백준] 1676번 : 팩토리얼 0의 개수

문제

 

---

풀이

 

저 문제 기준으로 10은 1이다. 100은 2고, 1000은 3이다.

즉 해당 팩토리얼을 계산했을 때 10이 몇번이나 곱해졌는지 세어보면 답이 나올 것이다.

 

10=2x5다. 그니까 팩토리얼을 계산했을 때 곱해진 2의 수와 5의 수를 각각 구해 그 중 작은 것을 택하면 된다.

---

소스코드

 

#include <iostream>
#include <algorithm>
using namespace std;

int fact(int N) {
    int two_cnt = 0, five_cnt = 0;

    for (int i = 2; i <= N; i *= 2)
        two_cnt += N / i;
    for (int i = 5; i <= N; i *= 5)
        five_cnt += N / i;

    return min(two_cnt, five_cnt); //2와 5가 모여야 한 쌍이므로 둘 중 작은 수로
}

int main() {
    int N;

    cin >> N;
    cout << fact(N);
}

코드는 굉장히 짧다.

다만,

 

    for (int i = 2; i <= N; i *= 2)
        two_cnt += N / i;
    for (int i = 5; i <= N; i *= 5)
        five_cnt += N / i;

이 부분이 이해안될 수도 있겠으니 설명을 하겠다.

 

10! 즉, N=10이라고 하자. 풀어쓰면 1x2x3x4x5x6x7x8x9x10이 되겠다.

i=2일 때 1~10까지의 수 중 2로 나눠 떨어지는 수들은 5개가 있다.

i=4일 때 1~10까지의 수 중 4로 나눠 떨어지는 수들은 2개가 있다.

i=8일 때 1~10까지의 수 중 8로 나눠 떨어지는 수들은 1개가 있다.

 

4=2^2이니까 엄밀히 말하면 2가 2개 들어있는 셈이다. 1개의 2는 i=2일 때 더해졌을 것이고, 나머지 1개의 2는 i=4일 때 더해졌을 것이다.

8=2^3도 i=2, 4, 8일 때 한 번씩 two_cnt에 더해졌을 것이다.

 

이해가 잘 안된다면 손으로 직접 해보는 것도 좋다.