백준, BOJ, 1676번 C++ [CPP]

10^승의 개수가

0의 개수란 것을 안다면

쉽다.

다만 숫자가 크기에..잘해봐야한다.

더군다나 시간제한도 있다

 

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

 

---

 

 

#맞는 풀이

#include<iostream>

using namespace std;

//0의 개수는 소인수분해 시 2와 5의 개수에 따라 결정된다.
//즉, 모든 숫자에 대해서 2,5의 개수파악, 근데 2의 개수가 압도적으로 많으므로 5의 개수만 파악하면 알아서 되겠다.

int dp[501];



int main(){
    
    int N;
    cin >> N;
    for(int i = 1; i<=N; i++){
        int cnt = 0;
        int temp = i;
        while(1){
            if(temp%5 == 0){
                cnt++;
                temp /= 5;
            }else{
                break;
            }
        }
        dp[i] = cnt;
    }
    int ans = 0;
    for(int i = 1; i<=N; i++){
        ans += dp[i];
    }
    
    cout << ans << '\n' ;
}

 

간단한 수학문제다.

안에 주석으로 답을 달아놨다.