[Algorithm]Baekjoon 2613번 :: 숫자구슬

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n, m;
int arr[301] = { 0 };
 
bool check(int maxBeadsScore)
{
    int groupCount = 1;
    int sum = 0;
 
    for (int i = 1; i <= n; ++i)
    {
        if (arr[i] > maxBeadsScore) return false;
 
        if (sum + arr[i] > maxBeadsScore)
        {
            ++groupCount;
            sum = arr[i];
        }
        else
        {
            sum += arr[i];
        }
 
        if (groupCount > m) return false;
    }
    return true;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
    }
 
    int left = 0;
    int right = n * 100;
    int answer = 0;
 
    while (left <= right)
    {
        int mid = (left + right) / 2; // 그룹당 최대구슬개수
 
        if (check(mid))
        {
            right = mid - 1;
            answer = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
 
    cout << answer << endl;
 
    vector<int> beadsCounts;
    int sum = 0;
    int start = 1;
    int maxBeadsCountIndex = 0;
 
    for (int i = 1; i <= n; ++i)
    {
        if (sum + arr[i] > answer)
        {
            beadsCounts.push_back(i - start);
 
            if (sum == answer)
            {
                maxBeadsCountIndex = beadsCounts.size() - 1;
            }
 
            start = i;
            sum = arr[i];
            
        }
        else
        {
            sum += arr[i];
        }
    }
 
    beadsCounts.push_back(n - start + 1);
    int splitCount = m - beadsCounts.size();
 
    if (splitCount > 0) 
    {
        vector<int> tempBeadsCounts;
 
        for (int i = 0; i < beadsCounts.size(); ++i)
        {
            int beadsCount = beadsCounts[i];
 
            if (i == maxBeadsCountIndex || splitCount == 0) // 기준덩어리이면
            {
                tempBeadsCounts.push_back(beadsCount);
                continue;
            }
 
            if (beadsCount > 1) // 분할여지가 있다면,
            {
                int size = beadsCount - 1;
                for (int j = 0; j < size; ++j)
                {
                    tempBeadsCounts.push_back(1);
                    --beadsCount;
                    --splitCount;
 
                    if (splitCount == 0 || beadsCount == 1) break;
                }
                tempBeadsCounts.push_back(beadsCount);
            }
            else
            {
                tempBeadsCounts.push_back(beadsCount);
            }
        }
 
        for (int i = 0; i < tempBeadsCounts.size(); ++i)
        {
            cout << tempBeadsCounts[i] << ' ';
        }
        return 0;
    }
 
    for (int i = 0; i < beadsCounts.size(); ++i)
    {
        cout << beadsCounts[i] << ' ';
    }
    
}
 
 
 

 

dp카테고리..에 있어서 dp테이블 고민했는데, 이분탐색으로 푸는 문제였다.

물론 dp테이블정립해서 풀수도 있는 문제일수도 있지만, 문제설명에서 이분탐색냄새가 풀풀 나는 문제였다...

 

탐색값(mid)을 각 그룹의 최대 구슬점수로 잡고, 해당 최대점수로만 그룹을 전부 묶었을 때 m개이하이면 true를 리턴하게하면 된다.

 

여기까지야 쉬운데, 이 문제에서의 포인트는 각 그룹의 개수까지도 출력해야 한다는 것.

오히려 여유로워서 m개를 전부 사용안하고도 묶어버릴 수 있는 경우, 일부러 쪼개서라도 그룹개수를 m개로 맞춰야하고 그걸 출력해야 한다.

나는 이부분을 거의 뭐 하드코딩수준으로 짜버렸는데... 이문제에 시간을 너무써서 그냥 넘어가려 한다.