케이블 길이를 최소화하는 컴퓨터-소켓 연결 방법의 수를 세는 C++ 프로그램

문제 설명

N개의 요소를 가진 두 배열 A와 B가 있다고 가정해 보겠습니다. 여기에는 N대의 컴퓨터와 N개의 소켓이 있으며, i번째 컴퓨터의 좌표는 A[i], i번째 소켓의 좌표는 B[i]입니다. 이 2N개의 좌표 값은 서로 모두 다르다고 가정합니다.

우리는 케이블을 사용해 각 컴퓨터를 소켓에 하나씩 연결하려고 합니다. 단, 각 소켓에는 최대 한 대의 컴퓨터만 연결할 수 있습니다. 이때 케이블 길이의 총합을 최소화할 수 있는 연결 방법이 총 몇 가지인지 구해야 하며, 답이 너무 커질 수 있으므로 10^9 + 7로 나눈 나머지를 반환합니다.

예를 들어 입력이 A = [0, 10], B = [20, 30]이라면 출력은 2가 됩니다. 최적의 연결 방식이 두 가지 존재하기 때문입니다. 하나는 (0→20, 10→30)이고, 다른 하나는 (0→30, 10→20)입니다. 두 경우 모두 케이블 길이의 총합은 40으로 동일합니다.

풀이 접근 방식

이 문제는 모든 좌표를 하나의 배열에 모아 정렬한 뒤, 컴퓨터는 +1, 소켓은 -1로 표시하여 한 번의 스캔으로 해결할 수 있습니다. 스캔 도중 누적 값(val)의 부호가 바뀌는 시점마다 매칭을 선택할 수 있는 경우의 수 |val|을 곱해 주면, 케이블 길이를 최소화하는 전체 연결 방법의 수를 효율적으로 계산할 수 있습니다.

구체적인 풀이 단계는 다음과 같습니다.

maxn := 200005
p := 10^9 + 7
정수형 쌍(pair)을 저장할 배열 하나를 정의합니다
n := A의 크기
i := 0부터 시작하여 i < n인 동안 i를 1씩 증가시키며 반복:
    a[i]의 첫 번째 값 := A[i]
    a[i]의 두 번째 값 := 1
i := n부터 시작하여 i < 2 * n인 동안 i를 1씩 증가시키며 반복:
    a[i]의 첫 번째 값 := B[i - n]
    a[i]의 두 번째 값 := -1
배열 a를 오름차순으로 정렬합니다
ways := 1, val := 0
i := 0부터 시작하여 i < 2 * n인 동안 i를 1씩 증가시키며 반복:
    만약 val * a[i].second < 0이라면:
        ways := ways * |val|
    val := val + a[i].second
ways를 반환합니다

C++ 구현 예제

아래 구현 예제를 통해 풀이 과정을 더 자세히 이해할 수 있습니다.

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

int solve(vector<int> A, vector<int> B){
    long maxn = 200005;
    long p = 1000000007;
    pair<int, int> a[maxn];
    int n = A.size();
    for (int i = 0; i < n; i++){
        a[i].first = A[i];
        a[i].second = 1;
    }
    for (int i = n; i < 2 * n; i++){
        a[i].first = B[i - n];
        a[i].second = -1;
    }
    sort(a, a + 2 * n);
    long long ways = 1, val = 0;
    for (int i = 0; i < 2 * n; i++){
        if (val * a[i].second < 0){
            ways = ways * abs(val) % p;
        }
        val += a[i].second;
    }
    return ways;
}
int main(){
    vector<int> A = { 0, 10 };
    vector<int> B = { 20, 30 };
    cout << solve(A, B) << endl;
}

입력

{ 0, 10 }, { 20, 30 }