BOJ 2004번 조합 0의 개수

BOJ : https://www.acmicpc.net/problem/2004

GitHub : https://github.com/junho0956/Algorithm/blob/master/2004/2004/%EC%86%8C%EC%8A%A4.cpp

 

이전에 풀었던 팩토리얼 0의 개수와 비슷한 문제이다.

조합을 통해 0을 만들 수 있는 조건이 무엇일까

1 3 7 9 같은 숫자로는 아무리 곱하고 나누어봐도 ..0 이라는 숫자를 만들 수가 없다.

=> 2와 5가 필요한게 이 문제의 핵심이다.

 

그럼 2와 5를 소인수분해를 통해서 개수를 알게된다면

어떻게 해야 0을 만들 수 있을까?

 

** 만약 2가 4개, 5가 3개라면 ==> 0은 3개가 나온다

** 만약 2가 7개, 5가 2개라면 ==> 0은 2개가 나온다

 

==> 2와 5의 갯수중 적은 숫자만큼 곱해야 0이 나오게된다.

 

#include <iostream>
using namespace std;
 
int solve(int size, int num) {
 
    int cnt = 0;
    while (size>=num) {
        cnt+=size/num;
        size /= num;
    }
 
    return cnt;
}
 
int main() {
    int n, m, five, two;
    cin >> n >> m;
 
    five = solve(n, 5) - solve(n - m, 5) - solve(m, 5);
    two = solve(n, 2) - solve(n - m, 2) - solve(m, 2);
 
    if (five >= two) cout << two;
    else cout << five;
 
    return 0;
}