JArchive 프로그래밍 일기

문제

조합 0의 개수 백준 2004번

리뷰

문제를 풀기 전에, 팩토리얼 0의 개수 문제를 다시 풀고 왔다.

아래는 조합을 구하는 식이다. 조합은 팩토리얼의 나눗셈과 곱셈으로 이루어져 있다.

그래서 이 문제는 n! 과 r! 과 (n-r)! 을 각각 계산해야 한다.

nCm의 끝자리 0의 개수는 10이 얼마나 곱해졌는지가 좌우한다.

10은 2x5 다.

그래서 n! 과 r! 과 (n-r)! 이렇게 3개의 팩토리얼에 2와 5가 몇 번 곱해져있는지 계산해야 한다.

five_cnt 함수는 5의 개수를 리턴한다. two_cnt 함수도 똑같은 구조다.

int five_cnt(int n){ // 5의 개수 구한다 
    int cnt = 0;

    for(long long i = 5; 1 <= (n/i); i *= 5){
        cnt += (n/i);
    }

    return cnt;
}

n과 m은 최대 2,000,000,000 의 숫자가 주어진다.

5를 곱해가면서 n을 나눌꺼니까 int의 표현범위를 넘을 것을 감안하여 long long 으로 선언한다.

two_cnt 함수는 2의 개수를 리턴한다.

two_cnt와 five_cnt 함수로 2와 5의 개수를 구하되, 둘 중에 작게 나온 값이 인수 10의 개수가 될 것이다.

n C r 조합에서 유의할 점 2가지

r == 0이면, 항상 1이다. 아무것도 안고르기 때문이다. n개중에 0개.

n == r 이면, 항상 1이다. 전부 고르기 때문이다. n개중에 n개.

따라서 n C m 이 주어졌을 때, m이 1인 경우, 2와 5의 숫자를 안구해도 된다. 어차피 1이기 때문이다.

n==m 인 경우에도 1이니까 2와 5의 숫자를 안구해도 된다.

    // 5, 2의 개수를 각각 구해서 작은 쪽을 출력한다
    five += five_cnt(n);
    if(m > 0) five -= five_cnt(m);
    if(n != m) five -= five_cnt(n-m);

맞은 코드

#include <iostream> 
#include <algorithm>

using namespace std;

int n, m;
int two, five;

int two_cnt(int n){ // 2의 개수 구한다 
    int cnt = 0;

    for(long long i = 2; 1 <= (n/i); i *= 2){
        cnt += (n/i);
    }

    return cnt;
}

int five_cnt(int n){ // 5의 개수 구한다 
    int cnt = 0;

    for(long long i = 5; 1 <= (n/i); i *= 5){
        cnt += (n/i);
    }

    return cnt;
}

int main(void){

    cin >> n >> m;     

    // 5, 2의 개수를 각각 구해서 작은 쪽을 출력한다
    five += five_cnt(n);
    if(m > 0) five -= five_cnt(m);
    if(n != m) five -= five_cnt(n-m);

    two += two_cnt(n);
    if(m > 0) two -= two_cnt(m);
    if(n != m) two -= two_cnt(n-m);

    cout << min(two, five);

    return 0;    
}