[ BOJ 백준 2613번 - 숫자구슬 ] 해설 및 코드

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

 

목적

<그림 1>과 같은 숫자구슬을 <그림 2>나 <그림 3>과 같이 M개의 그룹으로 나누었을 때, 그룹의 최대 합이 최소가 되도록 하는 값을 구하자.

문제 예시

접근법

1. 이분 탐색 알고리즘으로 1부터 전체 구슬의 합까지를 범위로 하여, 최적 값을 찾아나간다. 

2. 문제에서 분명하게 명시하진 않았지만, 직관적으로 그룹에 구슬이 하나도 없는 경우는 없어야 함을 인지한다. (M개의 그룹으로 나누라는 조건이 있으므로)

 

#include<iostream>
using namespace std;
 
int n, m, i, j, a[301] = { 0 }, b[300];
 
bool go(int lim) {
    int cnt = m;
    i = 0;
    while (i < n) {
        j = n - cnt + 1;
        while (i<j && a[j] - a[i]>lim)--j;
        if (i == j)return false;
        b[--cnt] = j - i;
        i = j;        
    }
    return cnt == 0;
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> a[i + 1];
        a[i + 1] += a[i];
    }
 
    int l = 1, r = a[n];
    while (l <= r) {
        int mid = (l + r) / 2;
        if (go(mid))r = mid - 1;
        else l = mid + 1;
    }
 
    cout << l << endl;
    go(l);
    for (int i = m - 1; i >= 0; --i)cout << b[i] << ' ';
}

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.