[알고리즘 연습] N!에서 0의 개수 (by. C++)

N!의 표현법

• 정수 N을 입력 받는다. (10<=N<=1000)
• N!의 결과에서 일의 자리부터 연속된 0의 개수를 구하시오. (ex. 5! = 120이므로 답은 1)

---

풀이

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

int main() {
    int i, n, tmp, s;

    cin >> n;
    vector<int> ch(n+1);

    for (i=2; i<=n; i++) {
        tmp = i;
        s = 2;
        while  (tmp != 1) {
            if (tmp % s == 0) {
                tmp = tmp / s;
                ch[s] += 1;
            } else {
                s += 1;
            }
        }
    }

    if (ch[2] < ch[5]) {
        cout << ch[2];
    } else {
        cout << ch[5];
    }

    return 0;
}

• 단순히 접근하면 안되는 문제다.
• N!을 단순히 계산해서 해결하려고하면 overflow가 날 가능성이 높다.
• 굳이 일의자리에서부터 연속된 0의 개수를 물은 이유를 잘 생각해야 한다.
• 일의자리에서부터 연속된 0의 개수는 소인수분해했을 때 5와 2를 곱해 생성된 10의 개수와 같다.
• 즉, 소인수분해 후 5와 2의 개수 중 더 작은 값이 0의 개수가 된다.