백준 2775번

BOJ 2775 : 부녀회장이 될테야

숫자를 나열해서 써보고 파스칼 삼각형이 보인다면 1차로 풀이가 어렵지는 않게 느껴진다

다만 단순히 팩토리얼만 이용해서 조합을 구현하면 계산과정에서 long long 자료형의 크기를 넘게 된다.

조합을 구하는 combination 함수를 따로 선언하고, combination 에서 조합의 성질을 이용하여 조합을 바꿔가며 계산을 용이하게 해준다

최대치인 $_{28}\mathrm{C}_{15}$ 에서 15! 을 계산하는 경우가 생기는데, 이는 int형에는 담기지 않고 long long 에만 담긴다.

int 형에 구겨넣으려고 시도해봤는데, 그냥 속편하게 long long 에서 마무리했다.

#include <stdio.h>

long long combination(int, int);

long long factorial(int);

int main()
{
    int T, k, n;
    while (scanf("%d", &T) != 1) continue;

    for (int i = 0; i < T; i++)
    {
        long long num_of_people;

        while (scanf("%d\n%d", &k, &n) != 2) continue;

        num_of_people = combination(n + k, 1 + k);

        printf("%lld\n", num_of_people);
    }
}

long long combination(int m, int n)
{
    if (n > m / 2)
        n = m - n;

    if (m > n && n > 1)
        return combination(m - 1, n - 1) + combination(m - 1, n);
    else
        return factorial(m) / (factorial(n) * factorial(m - n));
}

long long factorial(int N)
{
    long long result = 1;

    for (int i = 1; i <= N; i++)
        result *= i;

    return result;
}