[C++] 백준 2004: 조합 0의 개수

문제 이해

- nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하라.

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 128MB

 

<입력>

- 정수 n, m(0 ~ 2,000,000,000, 10^9, n != 0)

 

<출력>

- 첫째 줄에 nCm의 끝자리 0의 개수

 

 

---

문제 풀이

끝자리 0의 개수는 소인수 중 2와 5의 개수로 구할 수 있다!

둘 중 작은 것의 개수가 바로 끝자리 0의 개수이다.

 

 

 

nCm = n! / (n-m)! m! 이다.

즉, n!의 소인수 개수에서 (n-m)!과 m!의 소인수 개수를 빼주면 nCm의 소인수 개수가 나올 것이다.

 

 

 

그럼 n!의 소인수(k) 개수는 어떻게 구할 수 있을까?

일반적인 반복문을 사용하면 수의 크기가 워낙 크기에 시간 초과에 걸릴 수밖에 없다.

 

 

정답은 n을 k의 지수들로 나누어주는 것이다.

이러면 n!에 포함된 k 소인수의 개수를 구할 수 있다.

 

 

원리는 무엇일까?

n = 20, k = 2라고 했을 때를 보자.

 

20 / 2 = 10 (2, 4, 6, 8, ... , 20)

20 / 4 = 5 (4, 8, 12, 16, 20)

20 / 8 = 2 (8, 16)

20 / 16 = 1(16)

 

이렇게 할 수 있는 이유는 k가 여러 번 곱해진 수의 경우,

위의 예시처럼 그 횟수만큼 나누어 떨어지기에 점층적으로 합산이 되는 것이다.

 

 

---

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321

long long solve(int num, int mul){

    long long ans = 0;
    for(long long i = mul; i <= num; i *= mul){
        ans += num / i;
    }
    
    return ans;
}

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

    long long n, m;
    cin>>n>>m;

    long long num2, num5;
    num2 = solve(n, 2) - solve(n-m, 2) - solve(m, 2);
    num5 = solve(n, 5) - solve(n-m, 5) - solve(m, 5);

    cout<<min(num2, num5);
    return 0;
}

좋은 문제라고 생각되는 문제였다!

기본적인 수학 문제에 되게 약한 편인데 반성을 하게 만들어준 문제이다.