[BaekJoon/백준] 1676번

팩토리얼 값에서, 뒤의 0의 개수를 구하라는 문제다...

 

정말 어떻게 접근해야할지 모르겠어서 힌트를 봤는데, 소인수분해로 풀어나가는 거였다.

 

 

'뒤의 0의 개수'를 구하라는 것은 즉, 10 단위가 만들어질 때 마다 알아채야하는것인데, 10의 소인수는 2, 5 즉 2x5 이다.

그러므로, 범위 내에 존재하는 수들을 만날 때 마다 소인수 중 2와 5가 몇개 존재하는가를 알아내면 된다..

그러면 10을 몇번 만들 수 있는가를 알 수 있다.

 

(2x5) 를 한 쌍으로 봐야하므로, 둘의 갯수를 각각 구한 뒤 더 작은 갯수가 문제에서 원하는 0의 갯수에 대한 답이 된다.

#include <stdio.h>

int N;
int s_c;
int f_c;
int temp;


int main() {
    
    scanf("%d", &N);
    
    for(int i = 1; i <= N; i++) {
        
        temp = i;
        while(1) {
            if(temp % 2 == 0) {
                temp /= 2;
                s_c++;
            }
            if(temp % 5 == 0) {
                temp /= 5;
                f_c++;
            }
            if(temp % 2 != 0 && temp % 5 != 0)
                break;
        }
        
    }
    
    printf("%d", ((s_c<f_c)?s_c:f_c));
    
}