백준 1010: 다리 놓기

문제 소개

• 문제 번호: 1010
• 문제명: 다리 놓기
• 난이도 (티어): Silver V
• 사용 언어: C++
• 실행 시간: 8 ms
• 메모리: 2020 KB
• 문제 요약: 동쪽에는 N개의 작은 섬, 서쪽에는 M개의 작은 섬이 있습니다. 동쪽의 각 섬은 서쪽의 각 섬과 다리로 연결될 수 있습니다. 이때, 두 섬을 잇는 다리끼리 교차하지 않도록, 동쪽의 N개의 섬과 서쪽의 M개의 섬 사이에 총 N개의 다리를 놓는 경우의 수를 구하는 문제입니다. 단, 동쪽의 한 섬은 서쪽의 한 섬과 최대 하나의 다리만 연결될 수 있습니다.

접근 방법

이 문제는 결국 "M개의 섬 중에서 N개의 섬을 선택하여 다리를 놓는 경우의 수"를 구하는 것과 같습니다. 여기서 중요한 점은 다리가 교차하지 않아야 한다는 조건인데, 이는 M개의 섬 중 N개를 선택하는 순서가 정해지면 다리의 연결이 자동으로 결정된다는 의미를 내포합니다. 즉, M개의 섬 중 N개를 선택하는 조합(Combination) 문제입니다.

• 알고리즘/자료구조: 조합(Combination) 계산
• 선택 이유: 문제의 조건 자체가 "M개 중에서 N개를 선택하는 경우의 수"를 묻고 있으므로, 조합 공식을 직접 사용하는 것이 가장 효율적이고 직관적인 접근 방식입니다.

조합(Combination) 공식:
nCr = n! / (r! * (n-r)!)

하지만 이 공식을 그대로 사용하면 팩토리얼 값이 매우 커져서 오버플로우가 발생할 수 있습니다. 따라서, 계산 과정에서 오버플로우를 방지하고 정확한 정수 값을 얻기 위한 최적화된 조합 계산 방법이 필요합니다.

풀이 과정

문제에서 주어지는 T개의 테스트 케이스마다 N과 M이 주어집니다. 우리는 M개의 섬 중에서 N개의 섬을 선택하는 조합, 즉 M C N을 계산해야 합니다.

M C N = M! / (N! * (M-N)!)

이 공식을 그대로 구현하면 팩토리얼 계산으로 인해 오버플로우가 발생하기 쉽습니다. 이를 방지하기 위해, 조합 공식을 다음과 같이 변형하여 계산합니다.

M C N = (M * (M-1) * ... * (M-N+1)) / N!

이 식을 반복문으로 구현할 때, 곱셈을 먼저 수행하고 나눗셈을 수행하는 것이 중요합니다. 예를 들어, (M * (M-1)) / 2 와 같이 계산하는 것입니다. 이렇게 하면 각 단계에서 발생하는 중간 결과값이 nCr의 정의에 따라 항상 정수가 되므로, 정수 나눗셈으로 인한 오차 없이 정확한 결과를 얻을 수 있습니다.

핵심 아이디어:
M C N을 계산할 때, 팩토리얼을 직접 계산하는 대신 (M * (M-1) * ... * (M-N+1)) / N! 공식을 사용하고, 계산 과정에서 곱셈을 먼저 수행한 후 나눗셈을 수행하여 오버플로우를 방지하고 정확한 정수 값을 유지합니다.

주의할 점:

1. 오버플로우: 팩토리얼 값이 커질 경우 long long을 사용하더라도 오버플로우가 발생할 수 있습니다. 따라서, 앞서 설명한 res = res * (n - i + 1) / i; 방식이 중요합니다.
2. 정수 나눗셈: 중간에 정수 나눗셈이 먼저 일어나면 소수 부분이 버려져 결과가 틀려집니다. 반드시 곱셈을 먼저 수행해야 합니다.
3. 조합 대칭성: nCr = nC(n-r) 이므로, r 값이 n-r보다 크면 n-r로 계산하여 반복 횟수를 줄일 수 있습니다. (코드에서는 r > n - r 일 때 r = n - r 로 처리)

코드 설명

#include <bits/stdc++.h>
using namespace std;

// nCr 계산 함수
long long combination(int n, int r) {
    // 조합 대칭성을 활용하여 r이 n-r보다 클 경우 n-r로 계산하여 반복 횟수를 줄입니다.
    // 예: C(10, 7) = C(10, 3)
    if (r > n - r) r = n - r; 

    long long res = 1; // 결과를 저장할 변수 (long long 사용으로 오버플로우 방지)

    // r번 반복하며 조합을 계산합니다.
    // 공식: (n * (n-1) * ... * (n-r+1)) / (r * (r-1) * ... * 1)
    for (int i = 1; i <= r; i++) {

        // -----------------------------\
        // 1️⃣ 잘못된 방식 1: 정수 나눗셈 먼저
        // res *= (n - i + 1) / i;
        // 해석: (n-i+1)/i가 int / int → 정수 나눗셈 먼저 수행
        //      소수부가 날아가고 결과 틀림
        // -----------------------------\

        // -----------------------------\
        // 2️⃣ 잘못된 방식 2: 캐스팅 시도
        // res *= (long long)(n - i + 1) / i;
        // 해석: (long long)(n-i+1)/i → 나눗셈이 먼저 처리됨
        //      long long / int이지만 정수 나눗셈은 이미 수행되므로
        //      소수부는 버려짐
        //      곱하기 전에 나눗셈이 끝나 값이 틀림
        // -----------------------------\

        // -----------------------------\
        // 3️⃣ 잘못된 방식 3: double 사용
        // double dres = 1;
        // dres = dres * (n - i + 1) / i;
        // 해석:
        // - double로 계산하면 소수 연산 사용
        // - 큰 수에서는 정밀도 손실로 인해 정확한 정수값이 깨짐
        // - 조합 계산은 정수 연산이 필수이므로 double은 안전하지 않음
        // -----------------------------\

        // -----------------------------\
        // 4️⃣ 올바른 방식: 곱하기 먼저, long long 사용
        res = res * (n - i + 1) / i;
        // 해석: 
        // - res * (n-i+1)가 long long으로 계산
        // - 항상 정수
        // - 그 다음 / i로 나누면 정확한 정수 결과
        // - 소수부 손실 없음, C(n,r) 수학적으로 항상 정수이므로 안전
        // -----------------------------\
    }

    return res; // 계산된 조합 값을 반환
}

int main() {
    // 표준 입출력 속도 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T; // 테스트 케이스의 수
    cin >> T;

    // 각 테스트 케이스를 처리합니다.
    while(T--) {
        int N, M; // N: 동쪽 섬 개수, M: 서쪽 섬 개수
        cin >> N >> M;
        
        // M개의 섬 중 N개의 섬을 선택하는 경우의 수 (M C N)를 계산하여 출력합니다.
        // 문제에서 동쪽 섬 N개와 서쪽 섬 M개가 주어지고, N개의 다리를 놓는 경우의 수를 묻습니다.
        // 즉, M개의 서쪽 섬 중에서 N개를 선택해야 하므로 combination(M, N)을 호출합니다.
        cout << combination(M, N) << '\n'; 
    }
    return 0;
}

복잡도 분석

• 시간 복잡도: combination(n, r) 함수는 r번의 반복을 수행합니다. r은 n/2를 넘지 않으므로, 시간 복잡도는 O(min(N, M-N)) 입니다. 각 테스트 케이스마다 이 계산이 이루어지므로, 총 시간 복잡도는 T * O(min(N, M-N)) 입니다.
• 공간 복잡도: 조합 계산 시 상수개의 변수만 사용하므로, 공간 복잡도는 O(1) 입니다.

배운 점

이 문제를 통해 nCr 조합을 계산할 때 발생하는 오버플로우 문제를 효과적으로 해결하는 방법을 배울 수 있었습니다. 단순히 팩토리얼 공식을 그대로 적용하는 것이 아니라, 곱셈과 나눗셈의 순서를 조절하고 long long 타입을 적절히 활용함으로써 정확하고 효율적인 계산이 가능함을 알게 되었습니다.

또한, nCr = nC(n-r) 이라는 조합의 대칭성을 활용하여 반복 횟수를 줄이는 최적화 기법도 학습했습니다. 이는 앞으로 다른 조합 관련 문제를 풀 때 유용하게 적용될 수 있을 것입니다.

추가 팁

• 조합 문제는 다양한 알고리즘 문제에서 빈번하게 등장하므로, 효율적인 조합 계산 방법을 숙지하는 것이 중요합니다.
• dp[i][j] = dp[i-1][j] + dp[i-1][j-1] (파스칼의 삼각형)을 이용한 동적 계획법(DP)으로도 조합을 계산할 수 있지만, 특정 n, r에 대한 값을 구할 때는 위에서 사용한 반복문을 이용한 방법이 더 효율적일 수 있습니다.
• 문제에서 주어지는 입력의 범위를 항상 확인하여 적절한 자료형(int, long long)을 선택해야 합니다.