2613 숫자구슬

Link

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

Detail

당시 이분탐색 태그를 검색하고 들어온 문제라서 풀이법을 알 수 있었다. 태그를 모르고 풀었다면 아마 매우 고전했을 문제가 아니었을까.

각 그룹은 무조건 M개가 되어야 하는데, 이때 각 그룹의 숫자의 합의 최댓값이 최소가 되도록 분할하는 것이 목표다.

따라서, “각 그룹의 구슬 합이 a이하가 되도록 할 수 있는가?” 를 판단 함수로 잡고 매개변수 이분탐색을 돌리는 것이 해법이다. 단 이때 각 그룹은 최소한 하나의 구슬을 가져야 하므로, (판단 함수의 결과에는 영향이 없지만, 출력에서 각 그룹의 구슬 갯수를 반환해야 한다.) 이를 재배열 하는 과정까지만 걸쳐주면 문제를 해결할 수 있다.

Code

#include<bits/stdc++.h>  
  
using namespace std;  
  
#define DEBUG 1  
  
int BeadCount;  
int GroupCount;  
  
vector<int> Beads;  
  
// 각 그룹의 무게 합이 maxCapacity를 넘지 않도록 구슬을 그룹화하고, 그룹의 크기를 반환  
bool TryGroupBeads(int maxCapacity, vector<int>& groupSizes) {  
    groupSizes.resize(GroupCount, 0);  
    vector<int> groupWeights(GroupCount, 0);  
  
    int curGroup = 0;  
    for(int i = 0; i < BeadCount; i++) {  
       while(true) {  
          bool thisGroupAvailable = groupWeights[curGroup] + Beads[i] <= maxCapacity;  
  
          if(thisGroupAvailable) {  
             groupWeights[curGroup] += Beads[i];  
             groupSizes[curGroup]++;  
             break;  
          } else {  
             curGroup++;  
             if(curGroup >= GroupCount) {  
                return false;  
             }  
          }  
       }  
    }  
  
    //재조정 : 모든 그룹이 최소 하나씩은 가져야 함  
    for(int i = GroupCount - 1; i > 0; i--) {  
       if(groupSizes[i] <= 0) {  
          int need = 1 - groupSizes[i];  
          groupSizes[i] += need;  
          groupSizes[i - 1] -= need;  
       } else break;  
    }  
  
    return true;  
}  
  
void solution() {  
    int left = 0;  
    int right = accumulate(Beads.begin(), Beads.end(), 0);  
    int result = right;  
  
    while(left <= right) {  
  
       int mid = (left + right) / 2;  
       vector<int> groupResult;  
  
       if(TryGroupBeads(mid, groupResult)) {  
          result = mid;  
          right = mid - 1;  
       } else {  
          left = mid + 1;  
       }  
    }  
  
    vector<int> groupResult;  
    TryGroupBeads(result, groupResult);  
  
    cout << result << endl;  
    for(int i = 0; i < GroupCount; i++) {  
       cout << groupResult[i] << " ";  
    }  
}  
  
int main() {  
    cin >> BeadCount;  
    cin >> GroupCount;  
  
    Beads.resize(BeadCount);  
  
    for (int i = 0; i < BeadCount; i++) {  
       cin >> Beads[i];  
    }  
  
    solution();  
  
    return 0;  
}