[BAEKJOON] 1010번

 

다리가 겹치면 안 되므로 동쪽에서 뽑은 $M$개의 사이트 순서는 이미 정해져 있는 셈이다. 즉 $M$개 중에 $N$개를 뽑고 순서를 배열하지 않는 것이다. 따라서 $_MC_N = \frac{M(M-1)(M-2) \cdots (M-N+1)}{N!}$을 계산하면 된다.

 

..까지는 어렵지 않게 알 수 있다. 문제는 자료형의 한계다.

Python같은 경우 그냥 분자 계산하고 분모 계산해서 나누면 그만이지만 C의 경우 자료형을 벗어나는 경우가 생긴다.

$_{30}C_{15}$의 경우 $\frac{30\times29\times \cdots \times 16}{15!}$를 계산해야 하는데,

이 때 분자값은 $3,042,648,073,975,910,400,000$로 8바이트 자료형의 범위를 한참 벗어난다.

 

따라서 하나씩 계산해야 한다. $_{30}C_{15}=\frac{30\times29\times \cdots \times 16}{15!}$라면,

$30$을 곱하고 $1$로 나누고, $29$를 곱하고 $2$로 나누고,... 하는 식이다.

이 때 나머지가 무시되는 int형의 특성은 고려하지 않아도 된다. 어차피 분자와 분모에서 짝수와 홀수가 번갈아 나오기 때문이다.

 

또한 $_MC_N\;=\;_MC_{M-N}$임을 이용해 연산 횟수를 줄일 수 있다.

즉 $_{30}C_{26}$을 계산하려고 26번을 곱하는 게 아니라 $_{30}C_{30-26}\;=\;_{30}C_4$임을 이용해 4번만 곱하는 것이다. $N$이 $\frac{M}{2}$보다 클 때만 $_MC_{M-N}$을 계산하면 된다.

#include <stdio.h>
 
int main()
{
    int t, m, n;
    int lim, i, result;
 
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d %d", &n, &m);
        lim = ((n > m / 2) ? (m - n) : n);
        result = 1;
 
        for (i = 0; i < lim; i++)
        {
            result /= (i + 1);
            result *= (m - i);
        }
 
        printf("%d\n", result);
    }
    
    return 0;
}

12행

$N$이 $\frac{M}{2}$보다 크면 루프 횟수를 $M-N$으로, 아니면 $N$으로 설정한다.

 

13행

결과 값을 1로 초기화해야 곱하기/나누기 연산을 통한 $_MC_N$ 계산이 유효해진다.

 

17행 ~ 18행

Overflow를 막기 위해 곱하기보다 나누기를 먼저 수행한다.

또한 정수 연산은 나머지를 무시하므로 정확한 값을 유지하기 위해 분자는 큰 수부터, 분모는 작은 수부터 곱한다.