2004번

2004번 - 조합 0의 개수

우선 처음에 푼 방식으로는 시간초과가 발생했다. 이전에 팩토리얼의 0의 갯수 구하기 같은 문제는

범위가 작다보니 시간초과가 발생하지 않았지만, N의 범위가 20억이다보니 시간 초과가 발생하게 되었다.

그래서 다른 사람들의 코드를 보았더니, 더 쉽게 계산할 수 있는 방법이 있었다.

예를 들어 100! 에서 5가 몇개나 인수로 들어가있는지 계산하기 위해서는

100 / 5 + 100 / 25 + ... 이런식으로 계산을 해야한다.

25에는 5가 2개 들어있기 때문에, 125에는 3개 들어있기 때문에, 이런식으로 계산을 하면 쉽게 갯수를 구할 수 있다.

이와 같은 방식으로 코드를 구현하였다.

<문제점 발생>

==> N, M은 20억 이하의 숫자이기 때문에 N,M 은 int 형 자료를 썼다. 그런데 for문에서 선언한 모든 i 들은 이러한 N, M 보다 작다.

 

 그래서 처음에 문제 풀때 i 를 int 형으로 선언했는데, 그 때문에 런타임 오류가 발생했다.

 왜 그런지 질문 게시판에 올려놨다. 

해결>> 아... 난 바보였다... for문으로 들어오지 않더라도 오버 플로우가 발생할 수 있다는 걸 몰랐다니...

##추가답글##

  for문을 벗어나지 못할수도...

<정답 코드>

#include<iostream>
#include<algorithm>
using namespace std;
 
int main()
{
    int N, M;
    long long cnt2 = 0, cnt5 = 0;
 
    cin >> N >> M;
 
    for (long long i = 2; i <= N; i *= 2)
    {
        cnt2 += N / i;
    }
    for (long long i = 2; i <= M; i *= 2)
    {
        cnt2 -= M / i;
    }
    for (long long i = 2; i <= (N - M); i *= 2)
    {
        cnt2 -= (N - M) / i;
    }
 
    for (long long i = 5; i <= N; i *= 5)
    {
        cnt5 += N / i;
    }
    for (long long i = 5; i <= M; i *= 5)
    {
        cnt5 -= M / i;
    }
    for (long long i = 5; i <= (N - M); i *= 5)
    {
        cnt5 -= (N - M) / i;
    }
 
    cout << min(cnt2, cnt5) << endl;
 
    return 0;
}

<시간 초과 코드>

#include<iostream>
#include<algorithm>
using namespace std;
int N, M;
int cnt2 = 0;
int cnt5 = 0;
 
void plusCount(int n)
{
    for (int i = 1; i <= n; i++)
    {
        int x = i;
        while (x % 2 == 0)
        {
            cnt2++;
            x /= 2;
        }
 
        while (x % 5 == 0)
        {
            cnt5++;
            x /= 5;
        }
    }
}
void minusCount(int n)
{
    for (int i = 1; i <= n; i++)
    {
        int x = i;
        while (x % 2 == 0)
        {
            cnt2--;
            x /= 2;
        }
 
        while (x % 5 == 0)
        {
            cnt5--;
            x /= 5;
        }
    }
}
int main()
{
 
 
    cin >> N >> M;
 
    
    plusCount(N);
    minusCount(M);
    minusCount(N-M);
 
    cout << min(cnt2, cnt5) << endl;
 
 
    return 0;
}