[BOJ] 백준 2613 숫자 구슬

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

Binary Search (이분 탐색) 

Binary Search (이분 탐색)

[탐색] Parametric Search 

[탐색] Parametric Search

① 그룹의 합 중 최대값이 최소가 될 수 있는 최적해(mid)를 찾아야 합니다.

    즉, 최대값이 mid이하가 되도록 구슬을 나눌 수 있을까? 접근

    최소(left) = 원소 중 최대값, 최대(right) = 모든 구슬의 합에서 이분탐색 과정으로 찾아갑니다.

ex) arr = {5, 4, 2, 6, 9, 3, 8, 7}에서 원소 최대값 = 9 입니다. 

그렇기에 기준값을 9보다 작은것으로 설정이 된다면 원소 9는 어떤 그룹에도 들어가지 못하는 모순 발생하므로

따라서, 초기 low = 9(원소 최대값)이며, 그룹에 속한 구슬의 합의 최대값은 모든 구슬의 합 이하일 것이므로 high = 44 

 

② 이분탐색 과정에서 좌/우 영역 중 어떤 곳을 탐색할 지 고민합니다.

    주어지는 그룹 개수(M)을 만족하면 좀 더 작은 기준을 찾기 위해 좌측 영역 탐색

    그룹의 개수를 만족하지 못한다면 기준(mid)값을 크게 잡기 위해 우측영역 탐색

ex) 기준값(mid) 『26』 이라고 가정해보자.

[1 Group]: 5 + 4 + 2 + 6 + 9 = 26  ≤ 26

[2 Group]: 3 + 8 + 7 = 18 ≤ 26

나누어야 하는 그룹의 개수는 3개(= M)이며, 하나의 그룹에는 적어도 한 개의 구슬이 존재해야 합니다.

따라서 그룹을 {5 4 2 6 9}, {3 8}, {7} or {5 4 2 6 9}, {3}, {8 7}이든 어떻게든 균형을 맞출 수는 있습니다.

이 중 하나만을 출력하면 되므로, 왼쪽부터 최대한 채워넣되, 모든 그룹에 적어도 한개의 구슬이 있도록 합니다.

---

#include <iostream>
using namespace std;
 
int N, M;
int arr[300];
 
bool isPossible(int mid) {
    int sum = 0, groupCnt = 1;
    for (int i = 0; i < N; i++) {
        sum += arr[i];
        if (sum > mid){
            sum = arr[i];
            groupCnt++;
        }
    }
    return groupCnt <= M;
}
 
void printAns(int mid){
    cout << mid << '\n';
 
    int i, sum = 0, marbleCnt = 0;
    for (i=0; i < N; i++) {
        sum += arr[i];
        if (sum > mid) {
            sum = arr[i];
            M--;
            cout << marbleCnt << " ";
            marbleCnt = 0;
        }
        marbleCnt++;
        // M개의 그룹을 만들기 위해 최소한의 구슬은 남겨둡니다.
        // (나머지 그룹에 적어도 구슬 1개를 배치해야 하기 때문.)
        if (N - i == M) break;
    }
 
    // 위에서 구한 구슬 개수를 현재 그룹까지만 출력하고
    // 나머지 남은 그룹에는 구슬 1개씩 배치
    while (M--){
        cout << marbleCnt << " ";   
        marbleCnt = 1;
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    int left = 0, right = 0, mid;
    for(int i=0; i<N; ++i){
        cin >> arr[i];
        // 원소 중 최대값으로 left 설정
        left = left < arr[i] ? arr[i] : left;
        right += arr[i];
    }
        
    while (left <= right) {
        mid = (left + right) / 2;
        if(isPossible(mid))
            right = mid - 1;
        else
            left = mid + 1;
    }
 
    // 정답 출력
    printAns(left);
}