[BOJ 백준] 1676 - 팩토리얼 0의 개수 (C++)

문제 바로가기

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

1676번: 팩토리얼 0의 개수

 

---

 

관련 알고리즘

- 수학

---

정답 및 해설

정수 N을 입력받아 N!(N팩토리얼)을 계산하여 뒤에서부터 0이 아닌수가 나오기전까지 0의 개수를 세는 문제이다.

다소 난잡하지만 끝자리에 연속된 0의 개수를 세는 문제이다.

N=5 이면 5!=120으로 정답은 1, N=10 이면 10!=3628800으로 정답은 2인 것이다.

N이 최대 500이기 때문에 팩토리얼값을 직접 계산해서 정답을 구하기는 불가능하다.

따라서 끝자리에 0을 만드는 요소인 10의 약수, 즉 2와 5의 개수를 세서 정답을 구할 수 있다.

 

예를 들어 10!의 0의 개수는 10!에 곱해져있는 수들 중 2의 배수(2,4,6,8,10)와 5의배수 (5,10)를 통하여 구할 수 있다,

2,4,6,8,10에서 인수 2의 개수는 각각 1,2,1,3,1 총 8개

5,10에서 인수 5의 개수는 각각 1,1 총 2개

즉 1~10까지 곱하면서 10 인수는 최대 2개 등장하는 것이다.

---

C++

#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,k,tot[2]={0};
    cin>>N;
    for(int i=1;i<=N;i++){
        k=i;
        while(1){
            if(k%2==0){k/=2; tot[0]++;}
            else if(k%5==0){k/=5; tot[1]++;}
            else break;
        }
    }
    cout<<min(tot[0],tot[1]);
}

 

Line	해설
4	int N : 입력받을 정수 int tot[2] : 곱해진 숫자의 인수 중 2와 5의 개수
5~13	정수 N을 입력받은 후, for 반복문을 통해 i를 1부터 N까지 반복한다.
7~12	변수 k에 i를 대입한 후, while(1)으로 무한루프에 들어간다. if 조건문을 통해 k가 2의 배수이면 k/=2, tot[0]++를 통해 k에 2를 나누고, 2 인수의 개수를 1 증가시킨다. 그 다음 else if 조건문으로 k가 5의 배수일 경우, 같은 과정을 거친다. 만약 더 이상 2또는 5의 배수가 아니라면 break 문을 통해 무한루프를 빠져나온다.
14	2와 5의 개수 중 적은 개수를 구하여 정답을 구한다.