[Programmers] Lv0. 구슬을 나누는 경우의 수 | C++

🔗문제 링크

프로그래머스

 

 

👨‍💻풀이 과정

 

문제를 딱 읽어 봤을 때, 조합(Combination) 문제란 게 떠올랐습니다. C++ STL에는 순열과 조합을 구현해 놓은 라이브러리가 없나 찾아봤는데, next_permutation이라는 순열 라이브러리만 있더군요. 그래서, 그냥 직접 작성하여 풀어보기로 했습니다. 그런데, 문제가 될 만한 사항들이 다음과 같았습니다.

• balls와 share의 개수가 최대 30인데, 30!은 2.6525285981219105863630848e+32 라는 숫자가 나올만큼 어마어마하게 큽니다.
• 분수를 표현하기 위해, 나눗셈을 진행하다 보면 무한 소수처럼 떨어지지 않는 실수가 생기기도 합니다.

 

특히나 저 어마어마한 30!은 8byte 정수 자료형으로도 못 담을 것 같다는 생각이 들어서, 다른 풀이 전략이 없나 살펴보던 중 🔗좋은 힌트 글을 작성해주신 글을 발견하여 풀어보았습니다. 우선, 조합(Combination)의 공식은 다음과 같습니다.

 

조합 공식

 

1 ~ 30 중에 5개를 고르는 경우의 수는 위 공식을 이용하여 다음과 같이 쉽게 구할 수 있습니다.

 

(30 * 29 * 28 * 27 * 26) / 1 * 2 * 3 * 4 * 5

 

하지만 위와 같이 계산하면, 오버플로우가 날 수 있기에 나눗셈도 같이 적용하며, 숫자 크기를 줄여야 합니다.

 

(30 / 1) * (29 / 2) * (28 / 3) * (27 / 4) * (26 / 5)

 

하지만 위와 같이 연산을 진행한다면, 정수로 딱 나눠 떨어지지 않기에 부동소수점에서 계산이 틀릴 수 있습니다. n개의 연속된 정수들에는 항상 n의 배수가 포함됩니다. 이 사실을 이용하면 항상 정수값만 나오기에 소수점을 맞이하지 않을 수 있습니다.

 

(((((30 / 1) * 29 / 2) * 28 / 3) * 27 / 4) * 26 / 5)

 

 

잘 짠 코드라고 할 순 없겠지만, 좋은 힌트를 알려주신 글을 참고하여 코드를 작성해 보았습니다.

 

✏️소스 코드 및 결과

#include <string>
#include <vector>
using namespace std;

long Combination(int n, int r)
{
    long sum = 1;
    for (int i = 1; i < r + 1; i++)
    {
        sum = (sum * n) / i;
        n--;
    }
    return sum;
}

int solution(int balls, int share) {
    return Combination(balls, share);
}