[백준] 1010 다리놓기

어제부터 풀던 문제다. 어제 저녁 6시부터 새벽 6시까지 계속 고민하고 코딩했지만 풀지 못했다. 동아리 스터디를 하며 생각하고 집 오는 길에도 생각하고 집에 도착해서 그 방법을 시도해봤다. 

처음엔 규칙을 찾아서 해보려고 했으나 명확한 규칙이 나타나지 않았다. 그러다가 고등학생 때 배웠던 확률과 통계가 생각났고 교과서도 찾아 보며 조합을 이용하면 풀 수 있겠다는 것을 알아냈다. 

일반적으로 서로 다른 n개에서 순서를 생각하지 않고 r(n≤r)개를 택할 때, 이것을 n개에서 r개를 택하는 조합이라 하고, 이 조합의 수를 기호로 

nCr

와 같이 나타낸다.

 

위 문제에서 서쪽과 동쪽을 각자 n, m에 입력 받으면 mCn이 경우의 수이다.

처음에 나는 두 개의 변수 numerator(분자), denominator(분모)를 만들어 numerator에는 mPn을 대입하고 denominator에는 n!을 대입해서 numerator/denominator을 출력하려고 했다. 하지만 unsigned long long int 형으로 선언해줘도 값이 다 들어가지 않았다. 답답해서 구글에 문제에 대한 답도 검색해봤다. 하지만 내가 했던 방식과 달랐고 포기하지 않고 나는 내 방식으로 계속 시도했다. 

nCr = nCn-r   <-  이 원리를 이용하여 if 문을 추가해주었다.

아래는 내가 짠 코드이다.

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

int main(void)
{
    int i, j, n, m, t, r;
    long long int numerator;
    long long int denominator;
    long int *result;
    
    scanf("%d", &t);
    result = (long int*)malloc(sizeof(long int)*t);
    
    for (i=0; i<t; i++)
    {
        result[i] = 0;
        numerator = 1, denominator = 1;
        scanf("%d %d", &n, &m);
        
        if(m-n < n)
            n = m-n; 
        for (j=0; j<n; j++) {
            numerator *= m; 
            m -= 1; //분자
        }
        for (j=n; j>0; j--)
            denominator *= j; //분모
        result[i] = numerator / denominator;
    }
    
    for(i=0; i<t; i++)
        printf("%ld\n", result[i]); //long int 형은 %ld
    
    free(result);
    
    return 0;
}