문제

---

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

입력

---

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

출력

---

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

풀이

---

처음 문제를 풀고자 할 때 떠올릴 수 있는 방법은 직접 해당 N에 대한 Factorial 값을 구하여 끝의 자리부터 0 으로 끝나기 전까지의 Count 값을 구하면 된다고 생각할 수 있다.

그러나 Factorial 값은 더하기가 아닌 곱하기로 계속되어 연산된 값의 크기는 엄청나게 커지게 되고 이를 처리하기는 다소 힘들 수 있다. 결국 다른 방법을 접근해야 한다.

이때 문제 풀이에 힌트는 끝이 0으로 끝난다는 것에서 힌트를 얻을 수 있다.

말한대로 Factorial 은 연속된 곱셈으로 끝자리가 0으로 끝나는 곱셈은 결국 10이 곱해지는 경우를 생각할 수 있다.

예를 들어 6! 을 6 x 5 x 4 x 3 x 2 x 1 로 나열할 수 있는 데 5 x 2의 연산으로 10 이 생기고 10에 어떤 수를 곱하든 끝의 자리는 0이 되는 것을 알 수 있다.

따라서 Factorial 연산과정에 나오는 5 x 2의 개수 == 10승의 개수 를 구하면 된다.
이때 Factorial 의 특성상 5가 존재하면 그 아래 4, 3, 2 ... 는 존재하므로 10승이 만들어져
결국 연산과정에서 나올 수 있는 5의 개수를 세면 된다.

5의 거듭제곱이 등장하는 경우에는 10이 두 개가 만들어질 수 있으므로 이를 고려하게 되면
5의 거듭제곱만큼 끝자리 0의 개수가 증가하게 되는데
입력 값 N 의 범위는 500, 5^4 범위보다 작기 때문에 5^3 == 125 까지만 고려하면 된다.

이 문제는 입력 값 N 에 대한 Factorial 의 연산과정에서 5의 거듭제곱이 등장하는 경우를 Count 하면 된다.

코드

---

#include <iostream>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    int cnt = 0;

    cin >> n;

    while(n != 0)
    {
        if (n % 125 == 0)
            cnt += 3;
        else if (n % 25 == 0)
            cnt += 2;
        else if (n % 5 == 0)
            cnt++;
        n--;
    }
    cout << cnt;
    return 0;
}

Compact_Version

입력 값 N 이 감소하는 과정이 아닌 N 에 대한 5의 거듭제곱의 몫을 구하면 같은 방식으로 문제를 수행할 수 있게 된다.

#include <iostream>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    int cnt = 0;
    
    cin >> n;
    
    for(int i = 5; i <= n; i*=5)
    {
        cnt += (n / i);
    }
    cout << cnt;
    return 0;
}

느낀 점

자리수가 0으로 나오기 위해서 필요한 5 x 2 = 10 이라는 단순한 연산이 잘 떠오르지 않았다.
문제를 너무 어렵게만 생각하지말고 가장 단순하게 접근해보자