[C++] 백준 2004번 : 조합 0의 개수 (S2)

#문제

www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

#풀이 & 학습한 내용

supremo7.tistory.com/119에서는 2의 개수보다 5의 개수가 항상 적어서 5의 개수만 세어줬지만, 조합의 경우에는 2의 개수가 5의 개수보다 많을 수 있으므로 모두 세어주고 둘 중 최솟값을 답으로 출력해야 한다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
long long count5(long long N) {
    long long ans = 0;
    for (long long i = 5; i <= N; i*=5) {
        ans += N / i;
    }
    return ans;
}
 
long long count2(long long N) {
    long long ans = 0;
    for (long long i = 2; i <= N; i *= 2) {
        ans += N / i;
    }
    return ans;
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    long long N,M;
    long long n2 = 0;
    long long n5 = 0;
    cin >> N >> M;
    n2 += count2(N);
    n5 += count5(N);
    n2 -= count2(M);
    n5 -= count5(M);
    n2 -= count2(N-M);
    n5 -= count5(N-M);
    cout << min({ n2,n5 }) << '\n';
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Math/BOJ_2004.cpp

HoYoungChun/BOJ_algorithm