블로그 옮겼습니다

BOJ 1044번 팀 선발 본문

Algorithm/Problem Solving

BOJ 1044번 팀 선발

sgc109 2017. 5. 2. 16:59

https://www.acmicpc.net/problem/1044


\(2\leq{N}\leq{36}\) (N은 짝수)


N을 입력받고, 10^15 이하인 자연수를 N개씩 두줄 입력받는다.


N명의 사람은 1번팀 또는 2번팀에 들어간다. 각각의 사람이 어떤 팀에 들어갈 때 증가하는 팀의 전력이 주어진다.

1번팀과 2번팀가 같은 수의 팀원을 가지며 두 팀의 전력차가 최소가 되도록 팀을 배정할 때 각각의 사람이 어떤팀에

들어가게 되는지를 구하는 문제다.(만약 두 팀의 전력차가 같은 답이 여러개 있을 경우 사람들의 팀을 순서대로 나열한

sequence 가 사전순으로 앞서는 것을 출력. 예를 들어 2 1 1 2 와 2 1 2 1 이 있으면 2 1 1 2 를 출력)


일단 naive 하게 생각해 보면 N이 최대 36이기 때문에 각각의 사람이 둘중 한팀을 선택하기 때문에 2^36 가지의

분리 방법이 있는데 이 중에서 두 팀의 팀원 수가 같은 경우만 보고 전력 차가 최소가 되는 것을 답으로 구하면 

시간복잡도는 O(N*2^N) 가 될 것이다. 그런데 N이 최대 36이기 때문에 너무느리다.


여기서 시간을 줄일 수 있는 요소가 뭐가있을까?

우선 두 팀의 수가 다를 때도 모두 봐준다는 것이다.

이것을 통해 봐주는 수를 줄여 주기 위해 N명의 사람을 반띵해보자.

그래서 왼쪽 N/2 명의 사람들을 L그룹, 오른쪽 N/2 명의 사람들을 R그룹 이라고 해보겠다.

그럼 L그룹에서 1번팀에 들어가는 사람 수를 K라고 해보자. 그럼 R그룹에서 1번팀에 들어가는 사람 수는

N/2 - K 가 될 것이다. 그렇기 때문에 각각의 그룹에서 1번팀의 들어가는 사람의 수를 인덱스로 케이스를 분리해보자.

그럼 우선 각각의 그룹을 봐주는 데에 O(2^(N/2+1)) 이 걸릴 것이다. 

그럼 각각의 그룹을 봐서 뭘 어떻게 하느냐 하면

우선 1번팀에 들어갈때 생기는 전력을 +로, 그리고 2번팀에 들어갈때 생기는 전력을 -로 쳐보면

결과적으로 1번팀과 2번팀의 전력의 합이 0에 가장 가까운 답을 고르면 되는 문제로 변하게 된다.

그러면 L그룹에서 1번팀에 들어가는 사람을 K명으로 하면서 팀을 분배하는 방법이 있다고 치면

이 때의 전력의 합(실제로는 1번팀의 전력-2번팀의 전력)을 W라고 할 때,

R그룹에서는 1번팀에 들어가는 사람이 N/2-K명이면서 전력의합이 -W에 가장 가까운 경우를 고르면되는것이다!

그러면 실제 어떻게 분배했는지를 비트마스크로 표현해주고(1번팀에간 경우 0, 2번팀에 간 경우 1)

전력합과 이 비트마스크에 대한 정보를 1번팀에 간 사람수를 인덱스로 하는 벡터같은곳에 쌓아주면

L그룹을 분배해주는 모든 경우에 대해, 이 때의 전력합이 W, 1번팀에 간 사람수를 K라고하면

R그룹에서 N/2-K 인덱스에 해당하는 벡터같은 곳에서 이분탐색으로 -W와 가까운 후보 몇개만 봐주면 되는것이다.

물론 이분탐색을 하기 전에 1번팀에 들어간 사람 수로 나눠준 분배 방법들을 각각 자기네 덩어리끼리 모두 정렬해야 한다.


그럼 마지막으로 중요한 것은 이분탐색을 하고 정확히 어떤 것들을 후보로 봐줄 것이며, 

답이 여러개 일 때 사전순으로는 어떻게 하느냐는 문제가 있다.  우선 앞서 전력합과 분배한 상태 비트마스크를 쌍으로

벡터에 쌓아줬다. 그럼 어차피 1번팀에 간게 0이고 2번팀에 간게 1이기 때문에 사전순으로 먼저오는 것은 더 작다.

그러면 정렬을 할 때 어차피 비트 마스크로도 정렬이 되기 때문에 괜찮다..


라고 생각해서 한번 틀렸다. ㅠㅠ 이것은 앞서 말한 어떤 것들을 후보로 봐줄 것이냐에 대한 문제와 관련이 있는데

이분탐색을 한뒤 나오는 인덱스와 그 앞에꺼, 이렇게 총 두개를 봐주면 되는데 그 이유는

L그룹에서 어떤 분배방법의 전력합이 W라면 -W에 대해 이분탐색을 해서 찾은 위치 pos 를 보면

여기에서 전력합은 -W 이상일 것이다. 그러면 W와 -W 이상을 더할 텐데 그럼 W와 pos에서의 전력합의 합은

0이상이 나오게 되므로 pos+1 에서의 전력합과의 W의 합은 오히려 0에서 더 멀어진다.

하지만 좀만 생각해보면 pos-1은 더 답에 근접할 가능성이있다. (왜냐하면 lower_bound 특성상

더 작은놈은 지나치기 때문에 예를 들어 2 10 에서 3에 대해 lower_bound 를 하면 10을 찾는데

-3과 더해서 0에 가까운수는 2이라는 것만봐도 알 수가 있다.) W의 부호가 반대일 때도 같은 방법으로 마찬가지라는것을

증명할 수 있다.


어쨌든 lower_bound 를 해서 나온 pos와 그 앞에 꺼를 봐주는데 만약 단순히 bitmask 로 정렬되었으니 그냥 하면되겠지

라고 생각하여 이렇게 해보면, 사전순으로 나중에 오는것만을 보게될 수가 있다. 왜냐하면 pos과 pos-1의 전력합이

같으면서 pos-1보다 pos-2가 사전순으로 앞설 수가 있기 때문이다. 그리고 이건 pos-3, pos-4 등등 마찬가지일 가능성이

있기 때문에 단순히 몇개를 봐준다라고 생각하면 구현도 복잡해지고 느려질것이다.

그래서 전력합이 같을 때, 사전순으로 앞서는 분배 방법만을 유지시켜주면 이 문제를 해결할 수가 있는데

이미 같은 전력합이 있을 때 이것의 bitmast가 지금 쌓으려는 놈보다 사전순으로 앞서면 그냥 넣지말고 지나가며

만약 아니라면 삭제하고 나를 넣어서 같은 전력합에 대해 딱 하나의 방법만을 유지해준다.


이 때 map을 쓰면 편하다. 일단 자동으로 정렬을 해줘서 편하며, 그냥 전력합으로 find 해서 end()와 같은지 비교하면

이미 같은 전력합이 있는지 없는지 알 수 있음과 동시에, 만약 있다면 대입연산자로 쉽게 대체할 수 있기 때문이다.


이렇게 했을 때 시간복잡도는 우선 L,R 그룹을 봐주는데에 \(O(2^{\frac{N}{2}})\) 에

L그룹의 모든 분배방법에 대해서 lower_bound 와 map 에 삽입, 탐색등을 하므로 \(O(lgN)\). 총 \(O(2^{\frac{N}{2}}\cdot{lgN})\)

가 아니라.. 처음에 반띵해서 한 그룹에서 모든 방법들에 대해 N/2 개의 비트들을 돌아야 하기때문에

\(O(N\cdot2^{\frac{N}{2}})\) 가 드므로 이게 최종복잡도.


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
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
 
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
 
const ll INFL = 0x3c3c3c3c3c3c3c3c;
map<ll,ll> v[40][2];
ll score[2][40];
int N;
 
pair<ll, ll> merge(pair<ll, ll> A, pair<ll, ll> B){
    return make_pair(abs(A.first+B.first), (A.second<<(N/2))|(B.second));
}
int main() {
    inp1(N);
    FOR(i,2) FOR(j,N) scanf("%lld",&score[i][j]);
    FOR(j,N) score[1][j] *= -1;
    int l = N/2;
    int r = (N+1)/2;
 
    FOR(k,2){
        int lr = k?r:l;
        FOR(i,1<<lr) {
            ll diff = 0;
            int cntOn = 0;
            FOR(j,lr){
                int isOn = i&(1<<(lr-j-1))?1:0;
                diff += score[isOn][j+(k?l:0)];
                if(isOn) cntOn++;
            }
            if(v[cntOn][k].find(diff) != v[cntOn][k].end()) continue;
            v[cntOn][k][diff] = i;
        }    
    }
 
    pair<ll,ll> ans = {INFL,INFL};
    REP(i,0,N/2){
        for(auto it = v[i][0].begin(); it != v[i][0].end(); it++){
            auto target = -(*it).first;
 
            if(sz(v[N/2-i][1])==0continue;
 
            auto it2 = v[N/2-i][1].lower_bound(target);
            if(it2 != v[N/2-i][1].end()) {
                ans = min(ans, merge({(*it).first, (*it).second}, {(*it2).first, (*it2).second}));
            }
            if(it2 != (v[N/2-i][1]).begin()){
                --it2;
                ans = min(ans, merge({(*it).first, (*it).second}, {(*it2).first, (*it2).second}));
            }
        }
    }
 
    auto bit = ans.second;
    FOR(i,N) printf("%c ","12"[bit&(1ll<<N-1-i)?1:0]);
    return 0;
}
 
cs


Comments