[알고리즘/C++] 구슬을 나누는 경우의 수

# 문제 설명

머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.

# 제한사항

• 1 ≤ balls ≤ 30
• 1 ≤ share ≤ 30
• 구슬을 고르는 순서는 고려하지 않습니다.
• share ≤ balls

# 입출력 예

baslls	share	result
3	2	3
5	3	10

# 힌트

서로 다은 n개 중 m개를 뽑는 경우의 수 공식

 

# 문제 풀이

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// balls가 30이고 share가 15이면 계산과정에서 매우 큰 수가 나오기 때문에
// 매우 큰 수를 표현할 수 있는 __int128을 사용했습니다.
__int128 solution(int balls, int share) {
    __int128 answer = 0;
    
    // 경우의 수 공식을 그대로 표현하기 위해 세 부분으로 나누어 계산합니다.
    __int128 num1=1, num2=1, num3=1;
    
    // 분자의 n! 부분
    for(int i=1; i<=balls; i++)
        num1*=i;
    
    // 분모의 (n-m)! 부분
    for(int i=1; i<=balls-share; i++)
        num2*=i;
    
    // 분모의 m! 부분
    for(int i=1; i<=share; i++)
        num3*=i;
    
    // 각 부분을 계산합니다.
    return answer = num1 / (num2*num3);
}

 

# 경우의 수 계산 시간복잡도 줄이기

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

__int128 solution(int balls, int share) {
    __int128 answer = 0; 
    __int128 top=1, bot=1;

    __int128 num1 = balls-share > share ? balls-share : share;
    __int128 num2 = balls-share > share ? share : balls-share;
    for(int i = num1+1; i <= balls; i++) {
        top *= i;
    }
    for(int i = 1; i <= num2; i++) {
        bot *= i;
    }
    return answer = top / bot;
}

아래 표를 보면서 코드를 이해해주세요.

n=5, m=2 (balls - share > share ) 인 경우	n=5, m=3 (balls - share > share )가 아닌 경우