[백준 1010번] 다리 놓기 - 조합(Combination)

다이나믹 프로그래밍(Dynamic programming)을 사용한 풀이 보기

문제 설명

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

알고리즘

조합(Combination)

접근 방식 및 풀이

문제 조건을 보면, 서쪽 도시가 동쪽 도시보다 적거나 같다. 따라서 다리를 잇는 것은 동쪽 도시 중에서 서쪽 도시 개수만큼 고르는 것과 같다. 이는 M 개 중에서 N개를 고르는 방법의 개수라는 말인데 이럴 때 순열과 조합이 떠오를 것이다.

순열과 조합은 모두 경우의 수를 구한다는 공통점이 있다. 이 둘의 차이점은 순서 고려 여부에 있다. 순열은 순서를 고려하고 조합은 순서를 고려하지 않는다. 예를 들어 순열에서는 (1, 2, 3)과 (2, 1, 3)을 다른 경우로 생각하지만 조합에서는 이 둘을 같은 경우로 생각한다.

그렇다면 위와 같은 경우에는 순열과 조합 중에 어떤 것을 사용해야할까? 문제 조건에 힌트가 있다. 바로 ‘다리끼리는 서로 겹쳐질 수 없다’고 한 부분이다. 다리가 겹칠 수 없다면 순서가 고정될 수 밖에 없다.

따라서 M개 중에서 N개를 고르는 조합을 구하면 된다.

또한 주의할 점이 있다. 조합을 구할 때 최종 경우의 수는 크지 않지만 중간에 값이 너무 커져서 unsinged long long을 넘어갈 수가 있다. 이는 서쪽 도시의 개수가 너무 적을 때 일어난다. 그래서 M개 중에서 N개를 고르는 조합의 경우의 수와 M개 중에서 M-N개를 고르는 조합의 경우의 수가 같다는 것을 사용해 N이 M/2보다 작을 때 는 N 대신에 M-N을 사용해서 경우의 수를 구한다.

해당 문제는 다이나믹 프로그래밍(Dynamic programming)를 통해서도 풀 수 있다.

코드

문제 풀이에 사용한 언어: C

#include <stdio.h>

int main(){
    int qurry_n;
    int left, right;
    unsigned long long result = 1;
    
    scanf("%d\n", &qurry_n);
    
    for(int k = 0; k < qurry_n; k++){
        scanf("\n%d %d\n", &left, &right);
        result = 1;
        if(right / 2 < left) // 동쪽 도시 개수가 서쪽 도시 개수의 2배를 넘는다면
            left = right - left; // 서쪽 도시 개수를 변경(결과 값은 똑같지만 계산하는 숫자가 높아지지 않는다.)
        for(unsigned long long i = right; i > right - left; i--){ // 동쪽 도시에서 서쪽 도시 개수 만큼 고르는 경우의 수. 현재 경우의 수는 순서를 고려한 경우의 수가 된다.
            result *= i;
        }
        for(unsigned long long j = left; j > 1; j--){ // 순서를 고려하지 않는 경우의 수로 바꾼다.
            result /= j;
        }
        printf("%llu\n", result);
    }
    
    return 0;
}