프로그래머스 - 구슬을 나누는 경우의 수 - C++

https://school.programmers.co.kr/learn/courses/30/lessons/120840

프로그래머스

 

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

int arr[31];
int arr2[31];
long long cal(int f, int b)
{
    int cnt = 0, cnt2 = 0;
    long long num = 1;
    for (int i = f; i <= b; i++)
        arr[cnt++] = i;

    for (int i = 1; i <= b-f+1; i++)
        arr2[cnt2++] = i;

    for (int i = 0; i < cnt; i++)
    {
        for (int j = 0; j < cnt2; j++)
        {
            if (arr2[j] != 0 && arr[i] % arr2[j] == 0)
            {
                arr[i] = arr[i] / arr2[j];
                arr2[j] = 0;
            }
        }
    }
    for (int i = 0; i < cnt; i++)
    {
        if (arr[i] != 0)num *= arr[i];
    }
    for (int i = 0; i < cnt2; i++)
    {
        if (arr2[i] != 0)num /= arr2[i];
    }
    return num;
}

long long solution(int balls, int share) {

    return cal(share + 1, balls);
}

 

설명

서로 다른 n개의 구슬 중 m 개를 고르는 경우의 수는 공식으로 쉽게 해결할 수 있다.

n!/(n-m)!*m! 

이다.

하지만 n이 최대 30인 제한 조건에서 long long 의 범위를 벗어난다. 

따라서 최대한 계산할 때, 나누면서 계산해야한다. 

 

먼저 위의 공식은

(m+1 * m+2 * ... n) / ( n - m ) ! 

으로 줄일 수 있다.

 

하지만 이를 계산하여도 여전히 long long 의 범위를 벗어나게 된다. 

따라서 m+1, m+2... 를 곱셈하기 전에 바로바로 분모의 숫자들과 나누기를 진행한다. 

 

우리가 수학으로 분모를 계산할 때, 미리 약분을 진행하고 계산하는 것과 같은 원리이다. 

그러기 위해서  m+1 ~ n 까지의 수를 arr 배열에, 

1 ~ n-m 까지의 수를 arr2 배열에 저장한다.

 

그리고 2중 for문을 사용해 약분을 진행한다. 

 

for (int i = 0; i < cnt; i++)
    {
        for (int j = 0; j < cnt2; j++)
        {
            if (arr2[j] != 0 && arr[i] % arr2[j] == 0)
            {
                arr[i] = arr[i] / arr2[j];
                arr2[j] = 0;
            }
        }
    }

 

분모의 숫자들이 arr2 에 들어가있다. 분자의 숫자와 나눌 수 있고 약분이 진행되지 않았던 수라면 

약분을 진행한다. 그리고 arr2 배열의 나누기한 숫자는 0으로 바꿔 약분했다는 표시를 남긴다.

 

마지막으로 분자의 숫자를 전부 곱하고 분모의 숫자를 전부 나누기하면 답이 도출된다. 

 

for (int i = 0; i < cnt; i++)
    {
        if (arr[i] != 0)num *= arr[i];
    }
    for (int i = 0; i < cnt2; i++)
    {
        if (arr2[i] != 0)num /= arr2[i];
    }

 

 

항상 코딩 전에, 해당 변수의 범위를 예측해서 사용하는 습관을 들여야겠다.