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

문제: www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

 

문제풀이

 

입력 N에 대하여 N! 이 일의 자리부터 처음 0이 아닌 숫자가 나올 때까지의 0의 개수를 구하는 문제이다.

 

0의 개수는 N! 를 소인수 분해해서 성분 2와 5의 개수를 구한 다음 둘 중 더 작은 것의 개수를 출력하면 된다.

 

 

코드

#include <iostream>

using namespace std;

struct tf{ //2와 5의 개수
    int two;
    int five;
};

int func2(int num){ //2의 개수 구하기
    int cnt2 = 0;

    while(num%2==0){
        num /= 2;
        cnt2++;
    }

    return cnt2;
}

int func5(int num){ //5의 개수 구하기
    int cnt5 = 0;

    while(num%5==0){
        num /= 5;
        cnt5++;
    }

    return cnt5;
}

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

    int N;
    cin>>N;

    tf arr[501]; //0<=N<=500 이므로 501까지 선언

    for(int i=1; i<=N; i++){ //N까지의 숫자 각각 2와 5의 성분 개수를 구해준다.
            arr[i].two = func2(i);
            arr[i].five = func5(i);
    }

    int sum2=0, sum5=0;
    for(int i=1; i<=N; i++){ //팩토리얼이므로 성분 개수를 2, 5 각각 모두 더해준다.
        sum2 += arr[i].two;
        sum5 += arr[i].five;
    }

    cout<<min(sum2, sum5); //둘 중 작은 것 출력

    return 0;
}

 

 

결과