백준 1676: 팩토리얼 0의 개수(C++)

문제 링크 : https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

 

 

 

 

 

문제

 

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

입력

 

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

출력

 

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

 

 

 

해설

N!이면 1×2×3×4.....N-1×N 인데 이 결괏값에서 뒤에 0이 몇 개나 나오는지
구해야 한다.
예를 들어 5!이면 1×2×3×4×5=120으로 답은 1이고
10! 은 3628800으로 답은 2이다.

일단 가장 쉽게 생각해 볼 수 있는 것은 10을 곱할 때마다 뒤에 0이 하나 늘어나는 것이다. 그리고 5! 을 보면 5를 곱해도 0이 하나 늘어나는데 이는
5와 2가 만나 10을 이루기 때문이다. 엄밀히 말하자면 
5와 짝수만 만나도 일의 자리는 0이 되기 때문에 0이 하나 늘어난다.
10 또한 2 ×5로 5와 짝수가 만나기 때문에 0이 늘어나는 것이다.
즉 어떤 수를 소인수분해 했을 때 5가 존재하며 앞에 짝수가 곱해져 있을 시 
0이 하나씩 늘어난다.

팩토리얼을 구하면서 짝수는 수없이 곱해지고 있기 때문에
짝수는 신경쓸 필요는 없고 5가 몇 번 곱해졌는지만 확인하면 된다.

 

코드

#include<iostream>
using namespace std;
int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        int k=i;
        while(k%5==0)
        {
            ans++;
            k/=5;
        }
    }
    cout<<ans;
}

 

728x90

 

 

n을 입력받고 1부터n까지 모든 수를 탐색하면서 그 수가 몇개의 5로 이루어 졌는지 확인한다.

이는 9~14행 코드로 구현되어 있다. 어떤수를 5로 나눈 나머지가 0이면 이 수를 소인수분해 했을 때 5가 존재한다는 의미이므로 0의 개수가 하나 늘어난다. 이를 존재하지 않을 때 까지 반복한다.