[Problem Solving] BOJ 2613: 숫자구슬

문제 링크: https://www.acmicpc.net/problem/2613

 

인접한 구슬끼리 묶어서 그룹을 만든다. 각 그룹에는 한 개 이상의 구슬이 있다.

 

low: 구슬의 적힌 숫자 중 최댓값

high: 구슬의 적힌 숫자들의 합

으로 설정하고

low <= high를 만족하는 동안 다음을 반복한다.

mid는 (low + high) / 2이다.

1. 각 그룹의 구슬에 적힌 숫자의 합이 mid가 넘지 않도록 그룹을 만들었을 때, 발생하는 그룹의 수가 M보다 작거나 같다. -> 최소의 mid를 구하기 위해 범위를 더 낮춰본다. -> opt = min(opt, min), high = mid - 1

2. 각 그룹의 구슬의 적힌 숫자의 합이 mid가 넘지 않도록 그룹을 만들었을 때, 발생하는 그룹의 수가 M보다 많다. -> mid가 너무 작아서 너무 많은 그룹이 생겼으므로, 범위를 높여본다. -> low = mid + 1

 

그룹을 만드는 함수는 다음과 같이 수행된다.

i = 0..N의 루프를 수행 중 다음을 수행한다.

루프 시작

currentSum에 i번째 구슬에 적힌 숫자를 더한다.

currentSum이 x보다 크다면 그룹에 적힌 숫자의 합이 x를 초과한다면 currentSum을 i번째 구슬에 적힌 숫자로 초기화하고, result에 초과 직전 그룹의 크기를 result에 추가한다.

남은 구슬의 수와 만들어야 하는 그룹의 수가 같다면, 만들어야 하는 나머지 그룹에는 각각 남은 구슬이 하나씩 들어간다.

루프끝

마지막 그룹이 하나 남았다면 result에 추가해준다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
#define endl '\n'
using namespace std;

int N, M, opt = 987654321;
vector<int> beads;
vector<int> result;

void input()
{
    cin >> N >> M;
    beads.resize(N, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> beads[i];
    }
}

int test(int x)
{
    int currentSum = 0;
    int currentGroupSize = 0;
    int remainingGroups = M;

    for (int i = 0; i < N; i++)
    {
        currentSum += beads[i];

        // 그룹 합이 maxSumPerGroup를 초과하면 새로운 그룹 시작
        if (currentSum > x)
        {
            currentSum = beads[i];
            result.push_back(currentGroupSize);
            currentGroupSize = 0;
            --remainingGroups;
        }

        ++currentGroupSize;

        // 남은 구슬 수와 그룹 수가 같다면, 남은 구슬은 전부 한 개씩 나눈다
        if (remainingGroups == N - i)
        {
            result.push_back(currentGroupSize);
            --remainingGroups;
            for (int j = 0; j < remainingGroups; j++)
            {
                result.push_back(1);
            }
            return result.size();
        }
    }

    // 마지막 그룹 처리
    if (currentSum > 0)
    {
        result.push_back(currentGroupSize);
    }

    return result.size();
}

void solution()
{
    int low = 0;
    int high = 0;
    int mid;
    for (int i = 0; i < N; i++)
    {
        low = max(low, beads[i]);
        high += beads[i];
    }
    while (low <= high)
    {
        mid = (low + high) / 2;
        result.resize(0);
        int numOfDiv = test(mid);
        if (numOfDiv <= M)
        {
            opt = min(opt, mid);
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    result.resize(0);
    test(opt);
}

void output()
{
    cout << opt << endl;
    for (auto i : result)
    {
        cout << i << " ";
    }
    cout << endl;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solution();
    output();

    return 0;
}