[백준] 2613번 : 숫자구슬 (C++)

2613번 : 숫자구슬

---

문제)

N개의 숫자 구슬이 <그림 1>과 같이 막대에 꿰어져 일자로 놓여 있다. 이들 구슬은 막대에서 빼낼 수 없고, 바꿀 수 없다.

이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최댓값이 최소가 되도록 하려 하다. 예를 들어 세 그룹으로 나눈다고 할 때 <그림 2>와 같이 그룹을 나누면 그룹의 합은 각각 11, 15, 18이 되어 그 중 최댓값은 18이 되고, <그림 3>과 같이 나누면 각 그룹의 합은 각각 17, 12, 15가 되어 그 중 최댓값은 17이 된다. 숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최댓값이 17보다 작게 만들 수는 없다. 그룹에 포함된 숫자 구슬의 개수는 0보다 커야 한다.

각 그룹의 합 중 최댓값이 최소가 되도록 M개의 그룹으로 나누었을 때, 그 최댓값과 각 그룹을 구성하는 구슬의 개수를 찾아 출력하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 이하의 자연수이다.

 

 

출력 :

각 그룹의 합 중 최댓값이 최소가 되도록 M개의 그룹으로 나누었을 때 그 최댓값을 첫째 줄에 출력하고, 둘째 줄에는 각 그룹을 구성하는 구슬의 개수를 왼쪽부터 순서대로 출력한다. 구슬의 개수를 출력할 때는 사이에 한 칸의 공백을 둔다. 만약 그룹의 합의 최댓값이 최소가 되도록 하는 경우가 둘 이상이라면 그 중 하나만을 출력한다.

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m;
vector<int> vec;
vector<int> s;
 
bool check(int x)
{
    int cnt = 1;
    int total = 0;
    for (int i = 0; i < n; i++)
    {
        if (total + vec[i] <= x)
        {
            total += vec[i];
        }
        else
        {
            if (vec[i] <= x)
            {
                total = vec[i];
            }
            else
            {
                return false;
            }
            cnt++;
        }
    }
 
    return (cnt <= m);
}
 
int p_s()
{
    int s = 0;
    int e = 100000000;
 
    int ans = e;
    while (s <= e)
    {
        int mid = (s + e) / 2;
 
        if (check(mid))
        {
            ans = mid;
            e = mid - 1;
        }
        else
        {
            s = mid + 1;
        }
    }
 
    return ans;
}
 
void counting(int x)
{
    int cnt = 0;
    int total = 0;
 
    for (int i = 0; i < n; i++)
    {
        if (total + vec[i] <= x)
        {
            total += vec[i];
            cnt++;
        }
        else
        {
            s.push_back(cnt);
            total = vec[i];
            cnt = 1;
        }
    }
    s.push_back(cnt);
 
    // 맨 뒤에서 부터 보며
    // s의 갯수가 m이 되지 않는다면
    // 1보다 큰 맨 뒤의 요소를 나눠준다.
    while (s.size() < m)
    {
        for (int i = s.size() - 1 ; i > -1; i--)
        {
            if (s[i] > 1)
            {
                s.insert(s.begin() + i + 1, s[i] / 2);
                s[i] = s[i] - s[i] / 2;
                break;
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
 
    vec.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> vec[i];
    }
 
    int ans = p_s();
 
    cout << ans << '\n';
 
    counting(ans);
 
    for (auto nxt : s)
    {
        cout << nxt << " ";
    }
 
    return 0;
}
 

---

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

2613번: 숫자구슬