[Algorithm] cpp 백준 14560번: Communism

문제

링크: https://www.acmicpc.net/problem/14560
요약: N(≤30)개의 일을 린카루/아드/래리 세 사람에게 나눌 때, 아드와 래리의 총보수 합의 차이가 D를 넘지 않도록 하는 배분의 수를 구한다.
제한: N ≤ 30, 1 ≤ A_i ≤ 10^16, 0 ≤ D ≤ 10^18, 시간 1초, 메모리 512MB

입력/출력

1
2
3
4
5
6
7
<입력>
N
A1 A2 ... AN
D

<출력>
조건을 만족하는 서로 다른 배분 가짓수

예제 1

예제 2

접근 개요

각 일을 누구에게 주는지는 세 가지: 린카루(차이 0), 아드(차이 +A_i), 래리(차이 −A_i).
전체 배분은 (아드−래리) 차이 s에 대해 |s| ≤ D를 만족해야 한다. 린카루에게 가는 일은 차이 계산에 영향이 없다.
N ≤ 30에서 3^N 전탐색은 불가능하므로, 반으로 나누어(meet-in-the-middle) 각 절반에서 만들 수 있는 차이 값을 생성한다.
한쪽 리스트를 정렬한 뒤, 다른 쪽의 값 x에 대해 s2 ∈ [−D−x, D−x]인 원소 수를 이분 탐색으로 더한다.

Mermaid로 보는 흐름

flowchart TD
  A[일 목록 A] --> B[절반 분할 L/R]
  B --> C[왼쪽 L: (아드-래리) 가능한 합 S1 생성]
  B --> D[오른쪽 R: (아드-래리) 가능한 합 S2 생성]
  C --> E[S2 정렬]
  D --> E
  E --> F[각 x∈S1에 대해 S2에서 -D-x..D-x 범위 개수 합산]
  F --> G[정답]

알고리즘 설계

상태: 각 원소 A_i를 {0, +A_i, −A_i} 중 하나로 더한 누적값 s(=아드−래리).
분할: 정렬로 |A_i| 큰 것부터 배치해 강한 가지치기를 유도하고, 15/15로 분할.
가지치기(pruning): 인덱스 i 이후 남은 절대합 rem과 상대 절반의 절대합 other를 이용해, 가능한 최종 s의 구간 [cur−rem, cur+rem]이 [−D−other, D+other]와 교집합이 없으면 탐색 중단.
집계: S2만 정렬. 각 x∈S1에 대해 이분 탐색으로 S2에서 [−D−x, D−x] 개수를 더한다.
특수 처리: D ≥ sum(A)면 모든 배분이 유효이므로 3^N을 즉시 출력.

복잡도

시간: O(3^(N/2) log 3^(N/2)) ≈ O(3^(N/2)·N) + 가지치기 효과로 더 빠름.
공간: O(3^(N/2)) 리스트 두 개 저장.

구현 (C++)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

static inline long long pow3(int n){
    long long r = 1;
    for(int i=0;i<n;i++) r *= 3LL;
    return r;
}

static void gen_with_prune(
    const vector<long long>& vals,
    const vector<long long>& suffixAbs,
    int idx,
    long long cur,
    long long otherAbsSum,
    long long D,
    vector<long long>& out
){
    long long rem = suffixAbs[idx];
    if (cur - rem >  D + otherAbsSum) return;
    if (cur + rem < -D - otherAbsSum) return;

    if (idx == (int)vals.size()){
        out.push_back(cur);
        return;
    }
    gen_with_prune(vals, suffixAbs, idx+1, cur, otherAbsSum, D, out);          // Lin
    gen_with_prune(vals, suffixAbs, idx+1, cur + vals[idx], otherAbsSum, D, out); // Ad
    gen_with_prune(vals, suffixAbs, idx+1, cur - vals[idx], otherAbsSum, D, out); // Larry
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if(!(cin >> N)) return 0;
    vector<long long> A(N);
    for(int i=0;i<N;i++) cin >> A[i];
    long long D; cin >> D;

    long long totalAbs = 0;
    for(long long v: A) totalAbs += v;
    if(D >= totalAbs){
        cout << pow3(N) << '\n';
        return 0;
    }

    sort(A.begin(), A.end(), [](long long x, long long y){
        return llabs(x) > llabs(y);
    });
    int n1 = N/2;
    int n2 = N - n1;
    vector<long long> L(A.begin(), A.begin()+n1), R(A.begin()+n1, A.end());

    long long sumAbsL = 0, sumAbsR = 0;
    for(long long v: L) sumAbsL += llabs(v);
    for(long long v: R) sumAbsR += llabs(v);

    vector<long long> suffL(n1+1, 0), suffR(n2+1, 0);
    for(int i=n1-1;i>=0;i--) suffL[i] = suffL[i+1] + llabs(L[i]);
    for(int i=n2-1;i>=0;i--) suffR[i] = suffR[i+1] + llabs(R[i]);

    size_t capL = 1, capR = 1;
    for(int i=0;i<n1;i++) capL *= 3;
    for(int i=0;i<n2;i++) capR *= 3;
    vector<long long> S1; S1.reserve(capL);
    vector<long long> S2; S2.reserve(capR);

    gen_with_prune(L, suffL, 0, 0LL, sumAbsR, D, S1);
    gen_with_prune(R, suffR, 0, 0LL, sumAbsL, D, S2);

    sort(S2.begin(), S2.end());

    long long ans = 0;
    for(long long x: S1){
        long long lo = -D - x;
        long long hi =  D - x;
        auto itL = lower_bound(S2.begin(), S2.end(), lo);
        auto itR = upper_bound(S2.begin(), S2.end(), hi);
        ans += (long long)(itR - itL);
    }

    cout << ans << '\n';
    return 0;
}

구현 (Python, 스켈레톤)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
# 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
import sys
from bisect import bisect_left, bisect_right

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))
    D = int(input().strip())
    # 동일한 아이디어로 구현 가능. C++ 버전을 참고.
    # 시간 제한상 파이썬은 PyPy에서만 통과 가능할 수 있음.
    pass

if __name__ == "__main__":
    main()