린카루 마을의 일 분배 문제

문제 설명

린카루 마을에는 N개의 일이 있다. 각 일은 정해진 보수를 가지고 있으며, 이를 린카루, 아드, 래리 세 명에게 나누어야 한다. 아드와 래리는 공평함을 중요시하기 때문에, 이들의 보수 차이가 D를 넘지 않도록 해야 한다. 일을 나누는 방법의 수를 구하는 것이 목표이다.

모든 가능한 일 분배 방식 중 아드와 래리의 보수 합 차이가 D를 넘지 않는 경우를 찾아야 한다. 각각의 분배는 린카루, 아드, 래리 중 누가 어떤 일을 맡았는지에 따라 서로 다른 경우로 간주된다.

해결 아이디어

1. 부분집합 합을 활용한 Meet-in-the-Middle 접근

• ( N )의 최대 크기가 30이므로, 이를 절반으로 나누어 각 절반에서 가능한 모든 부분집합의 합을 구한다.
• 왼쪽 부분과 오른쪽 부분의 합을 조합하여 보수 차이 조건을 만족하는 경우의 수를 계산한다.

2. 중복 연산 제거 및 효율적 탐색

• 각각의 부분집합 합은 세 가지 경우로 나뉜다:
  1. 린카루가 맡은 경우
  2. 아드가 맡은 경우 (음수 방향)
  3. 래리가 맡은 경우 (양수 방향)
• 왼쪽과 오른쪽 부분집합 합을 병합하여 정렬된 상태로 유지함으로써 이진 탐색을 활용한다.

코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#define int int64_t

int32_t main() {
    fastio;
    
    // 입력 크기 및 초기화
    int size; 
    cin >> size;
    vector<int> numbers(size);
    for (int i = 0; i < size; i++) cin >> numbers[i];
    int threshold; 
    cin >> threshold;

    // 크기가 1인 경우 즉시 종료
    if (size == 1) 
        return !(cout << (numbers[0] <= threshold ? 3 : 1) << '\n');

    // 부분 배열의 가능한 합을 계산하는 함수
    auto calculateSubsets = [&](int left, int right) -> vector<int> {
        auto dfs = [&](int index, auto&& dfs) -> vector<int> {
            if (index > right) return { 0 }; // 끝까지 탐색했으면 0 반환
            auto subset1 = dfs(index + 1, dfs); // 현재 숫자를 포함하지 않는 경우
            auto subset2 = subset1, subset3 = subset2;
            for (auto& val : subset2) val -= numbers[index]; // 현재 숫자를 빼는 경우
            for (auto& val : subset3) val += numbers[index]; // 현재 숫자를 더하는 경우
            vector<int> result; 
            result.reserve(subset1.size() + subset2.size() + subset3.size());
            
            // 세 개의 배열을 병합하여 정렬 상태 유지
            for (int i1 = 0, i2 = 0, i3 = 0; 
                 i1 < subset1.size() || i2 < subset2.size() || i3 < subset3.size();) {
                if (i1 < subset1.size()
                    && (i2 == subset2.size() || subset1[i1] <= subset2[i2])
                    && (i3 == subset3.size() || subset1[i1] <= subset3[i3])) result.push_back(subset1[i1++]);
                if (i2 < subset2.size()
                    && (i1 == subset1.size() || subset2[i2] <= subset1[i1])
                    && (i3 == subset3.size() || subset2[i2] <= subset3[i3])) result.push_back(subset2[i2++]);
                if (i3 < subset3.size()
                    && (i1 == subset1.size() || subset3[i3] <= subset1[i1])
                    && (i2 == subset2.size() || subset3[i3] <= subset2[i2])) result.push_back(subset3[i3++]);
            }
            return result;
        };
        return dfs(left, dfs);
    };

    // 배열을 두 부분으로 나누어 각각 처리
    auto leftSums = calculateSubsets(0, size / 2 - 1);
    auto rightSums = calculateSubsets(size / 2, size - 1);

    // 정답 계산
    int count = 0;
    for (int i = 0, leftIndex = 0, rightIndex = 0; i < leftSums.size(); i++) {
        while (rightIndex < rightSums.size() && rightSums[rightIndex] <= leftSums[i] + threshold) rightIndex++;
        while (leftIndex < rightSums.size() && rightSums[leftIndex] < leftSums[i] - threshold) leftIndex++;
        count += rightIndex - leftIndex;
    }

    // 결과 출력
    cout << count << '\n';
}

코드 설명

1. 입력 처리:

   • (N)과 (A) 배열을 입력받는다.
   • 입력 크기가 작으면 단순히 세 명으로 나눠 경우를 반환한다.

2. 부분집합 합 계산:

   • 입력 배열을 두 부분으로 나누어 모든 가능한 부분집합 합을 계산한다.
   • 각 부분집합 합은 "린카루", "아드", "래리"에 해당하는 경우로 분리.

3. 결합 및 계산:

   • 왼쪽 부분과 오른쪽 부분을 이진 탐색을 활용하여 결합.
   • threshold 조건을 만족하는 쌍을 효율적으로 계산.

So...

이 코드는 (O(3^{N/2} \log(3^{N/2}))) 복잡도로 문제를 해결한다.
Meet-in-the-Middle 기법을 활용하여 입력 크기를 절반으로 줄이고, 정렬 및 이진 탐색으로 효율적인 계산을 수행했다.
이 접근법은 작은 입력에서부터 매우 큰 입력까지 확장 가능하며, 조건을 만족하는 모든 조합을 빠르게 탐색할 수 있다.