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

#문제

1676번: 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

 

---

#접근방법

N!은 1부터 N까지의 숫자의 곱을 의미한다. N!의 0의 개수를 구하려면 10의 약수인 2와 5의 개수를 먼저 구해줘야한다.

반응형

---

#풀이

#include <stdio.h>

int main(){
    int n;
    int a=0,b=0;
    int ans;

    scanf("%d",&n);

    for(int i=2;i<=n;i++){
        int x = i;

        while(x%2==0){
            x/=2;
            a++;
        }
        while(x%5==0){
            x/=5;
            b++;
        }
    }

    if(a<b) ans = a;
    else ans = b;

    printf("%d",ans);

    return 0;
}

 

위에서 설명했듯이 10의 약수인 2와 5의 개수를 먼저 구해줘야한다. 그리고 2와 5의 개수 중 작은 값을 출력하면 정답이다.

 

N!의 0의 개수는 10이 얼마나 곱해져 있는지를 구하는 문제랑 같기 때문이다.

 

먼저 scanf로 n을 입력받고 2부터 n까지 for문을 돌아준다.

 

그리고 i값을 직접 나누면 for문의 조건이 이상해지므로 변수 x에 i값을 넣어주어서

 

while반복문에서 x가 2로 나눠질 경우, x가 5로 나눠질 경우에 x를 나눠주면서 2와 5의 개수를 a,b에 각각 저장시켜준다.

 

그리고 a와 b중 작은 값을 ans에 저장하고 출력하면 정답이다.

---

#성능

---

#정리

N!이 어떤의미를 가지고 있는지 아는 것,

 

N!의 0의 개수는 10이 얼마나 곱해져 있는지 구하는 것을 알고 있다면 쉽게 풀 수 있는 문제였다.