[BOJ/백준] 2004 조합 0의 개수

● [문제번호 2004] 조합 0의 개수

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

2004번: 조합 0의 개수

 

● 알아야 할 것

: //

 

● 풀이 과정

: [1676 팩토리얼 0의 개수] 문제에서 변형된 문제이다.

: 조합은 팩토리얼의 표현으로 만들 수 있으므로 이를 활용하여 풀이를 한다.

: '같은 밑을 가지는' 두 수의 곱은 '지수의 합' 으로 계산하고

'같은 밑을 가지는' 두 수의 나누기는 '지수의 차' 로 계산한다.

 

● 주의 할 것

: 2의 지수와 5의 지수를 구할 때 N, M이 20억까지 주어질 수 있으므로 long long형을 선언하여 int형의 범위를 벗어난 경우에 '런타임 에러' 가 나타나지 않도록 한다.

 

● 참고 할 것

: 조합의 수학적 지식

팩토리얼이 있는 오른쪽 우항을 주목해주세요.

https://ko.wikipedia.org/wiki/%EC%A1%B0%ED%95%A9

 

: 이전 문제의 코드 활용

https://pirateturtle.tistory.com/187

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

int N, M, cnt;

// 숫자의 뒷자리 0은 2와 5의 곱을 통해 나온다
// 주어진 수에 2가 몇개 들어있는 지
// 주어진 수에 5가 몇개 들어있는 지
// 확인하여 작은 갯수를 출력하면 된다
void count_zero()
{
    // 2가 몇개 들어있는 지
    // 5가 몇개 들어있는 지
    int two_cnt = 0;
    int five_cnt = 0;
    
    // N! 의 2, 5의 지수를 구하는 과정
    for(long long two = 2; two <= N; two *= 2)
        two_cnt += N / two;
    
    for(long long five = 5; five <= N; five *= 5)
        five_cnt += N / five ;
    
    // M! 의 2, 5의 지수를 구하는 과정 (기존 지수의 갯수에서 차감)
    for(long long two = 2; two <= M; two *= 2)
        two_cnt -= M / two;
    
    for(long long five = 5; five <= M; five *= 5)
        five_cnt -= M / five ;
    
    // (N - M)! 의 2, 5의 지수를 구하는 과정 (기존 지수의 갯수에서 차감)
    for(long long two = 2; two <= N - M; two *= 2)
        two_cnt -= (N - M) / two;
    
    for(long long five = 5; five <= N - M; five *= 5)
        five_cnt -= (N - M) / five ;
    
    
    // 2의 지수와 5의 지수 중에 작은 수만큼 0이 생긴다
    cnt = min(two_cnt, five_cnt);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    
    count_zero();
    
    cout << cnt;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [300 - 수학 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	10430	나머지	https://pirateturtle.tistory.com/180
2	2609	최대공약수와 최소공배수	https://pirateturtle.tistory.com/181
3	1934	최소공배수	https://pirateturtle.tistory.com/182
4	1978	소수 찾기	https://pirateturtle.tistory.com/183
5	1929	소수 구하기	https://pirateturtle.tistory.com/184
6	6588	골드바흐의 추측	https://pirateturtle.tistory.com/185
7	10872	팩토리얼	https://pirateturtle.tistory.com/186
8	1676	팩토리얼 0의 개수	https://pirateturtle.tistory.com/187
9	2004	조합 0의 개수	https://pirateturtle.tistory.com/188