[백준] BOJ 1578 : 세계 정복

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

1578번: 세계 정복

 

문제의 조건을 요약하자면 아래와 같습니다.

 

1. N개의 국가가 있으며 각 나라마다 인구 수가 주어집니다.
2. 그룹이란 K명으로 이루어지며, 그룹 내의 사람들의 국적은 전부 달라야 합니다.
3. 문제에서는 그룹을 최대 몇 개로 나눌 수 있는지를 물어봅니다.

 

일단 관찰을 해봅시다. 그룹을 G개로 쪼갤 수가 있다면, 맨 마지막 그룹을 버림으로써 G-1개로도 쪼갤 수 있는 걸 알 수 있습니다. 그렇다면, 특정 G값을 초과하는 것부터는 그룹을 만들 수 없다는 걸 알 수 있습니다. 이러한 점을 활용해서 매개 변수 탐색을 사용할 수 있음을 알 수 있습니다.

 

그렇다면, 특정 G값에 대해서 그룹을 만들 수 있는 여부를 어떻게 파악할 수 있을까요? 일단, 각 나라 사람들은 그룹마다 최대 한 명씩 들어갈 수 있으므로 특정 나라 사람의 수가 a명이면 min(a,G)명이 들어갈 수 있을 겁니다. 이를 전부 합했을 때, K*G 이상이 된다면 그룹을 생성할 수 있습니다. 첫 번째 나라 사람들을 1 ... min(a,G)번 그룹까지 넣고, 이어서 두 번째 나라 사람들을 순서대로 집어넣고를 반복하다 보면 K명의 그룹 G개는 채워집니다.

 

따라서 총 시간복잡도는 O(Nlog(N*1000000000))가 됩니다. 매개 변수 탐색을 하는데, 그룹 최대 갯수를 대략 1000000000 * N이라고 잡으면 O(log(N* 1000000000))이 될텐데 각 mid 값마다 O(N)으로 그룹을 만들 수 있는지를 파악해야 하니 시간복잡도가 저리 됩니다. 코드는 아래와 같습니다.

#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
int main(){
    ll N,K,ans = 0;
    cin >> N >> K;
    vector<ll> v(N);
    for(int i=0; i<N; i++){
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    ll l = 0, r = 1e13;
    while(l+1 < r){
        ll mid = (l+r) / ((ll)2);
        ll result = 0;
        for(int i =0; i<N; i++){
            result += min(v[i], mid);
        }
        if(result >= (ll)mid * K) l = mid;
        else r= mid; 
    }
    cout << l;
} // Parametric Search

이 문제는 제가 예전에 풀었던 문제였는데, 관찰이 꽤 힘들었던 문제로 기억합니다. 그만큼 풀었을 때 쾌감이 있었던 문제기도 하고 '이렇게도 매개 변수 탐색을 할 수 있구나'라는 생각이 들던 문제였습니다. 비슷한 문제로는 BOJ 1561번도 있네요.