백준 2004번 조합 0의 개수

문제 링크입니다: https://www.acmicpc.net/problem/2004

숫자의 끝자리 0의 개수는 소인수 분해했을 때 min(2의 개수, 5의 개수)입니다.

우선, 조합의 공식을 살펴봅니다.

nCm = n! / (m!(n-m)!)이기 때문에 우리가 원하는 결과는 min(n!의 2의 개수 - m!의 2의 개수 - (n-m)!의 2의 개수, n!의 5의 개수 - m!의 5의 개수 - (n-m)!의 5의 개수)입니다.

하지만 주어진 숫자는 최대 2,000,000,000이기 때문에 브루트 포스로 2의 개수와 5의 개수를 구한다면 TLE가 발생합니다.

2와 5의 개수를 빠르게 구하기 위해서는 반복문을 조금 변형시켜야하는데 알고리즘은 아래와 같습니다.

알고리즘을 일반화시키기 위해 구하는 숫자를 i라고 하겠습니다.

1. 우선 N개의 숫자 중 반은 짝수이기 때문에 i의 개수에 N/i만큼 더합니다.

2. i^2의 배수 같은 경우 i로 나눈다고 해도 또 i가 남아있기 때문에 i의 개수에 N/(i^2)만큼 더합니다.

3. i^3의 배수 같은 경우 i^2로 나눈다고 해도 또 i가 남아있기 때문에 i의 개수에 N/(i^3)만큼 더합니다.

4. 이후 같은 과정 반복

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

pair<long long, long long> numOfZero(long long N)

{

        long long two = 0, five = 0;

        for (long long i = 2; i <= N; i *= 2)

                 two += N / i;

        for (long long i = 5; i <= N; i *= 5)

                 five += N / i;

 

        return { two, five };

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        long long N, M;

        cin >> N >> M;

 

        vector<pair<long long, long long>> v(3);

        v[0] = numOfZero(N); //N!

        v[1] = numOfZero(M); //M!

        v[2] = numOfZero(N - M); //(N-M)!

        cout << min(v[0].first-v[1].first-v[2].first, v[0].second-v[1].second-v[2].second) << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~