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

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

 

 

이 문제는 N개의 구슬이 존재하고 M개의 그룹의 수가 존재한다. 이때 N개의 구슬을 M그룹으로 나누어 각각의 구슬의 최댓값의 최소를 구하고 이때 만들어진 구슬의 M그룹의 개수를 구하는 문제이다.

 

최대를 최소로 만들기 위해서 어떻게 해야할까를 생각해보았다.

 

그럼 최댓값을 임의로 설정해서 최댓값 까지 도달했을때 다시 나눠서 0으로 만들어 더하는 방법을 생각하였다.

 

이때 이 최댓값을 더욱 빠르게 찾기 위해서 이분탐색을 생각하였다.

 

 

결국 최대로 설정하여 M만큼 나눌 수 있으면 최댓값을 더 늘릴 수 있다는 의미이므로 따로 check 함수를 만들어 나눈 그룹의 개수가 M보다 작은 경우 false로 left를 mid로 옮겨주었다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

struct horse {
    int x;
    int y;
    int dir;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
// int dx[] = {0, 0, 1, -1};
// int dy[] = {1, -1, 0, 0};
int dx[] = {1, 1, 1};
int dy[] = {-1, 0, 1};
int N, M;
int arr[301];

bool check(int mid) {
    int groups = 1;
    int sum = 0;

    for(int i = 0; i < N; i++) {
        if(arr[i] > mid) return false;

        if(sum + arr[i] > mid) {        // 중간값보다 큰 경우 그룹 나눠줘야함
            groups++;
            sum = arr[i];
        }
        else sum += arr[i];
    }

    return groups <= M;
}

void solve() {
    int left = 0;
    int right = 1e9;

    while(left +1 < right) {
        int mid = (left + right) / 2;

        if(check(mid)) {
            right = mid;
        }
        else {
            left = mid;
        }
    }

    cout << right << endl;

    int sum = 0;
    int cnt = 0;
    for(int i = 0; i < N; i++) {
        sum += arr[i];
        if(sum > right) {
            sum = arr[i];
            M--;
            cout << cnt << " ";
            cnt = 0;
        }
        cnt++;
        if(N - i == M) break;
    }
    while(M--) {
        cout << cnt << " ";
        cnt = 1;
    }
}

void input() {
    cin >> N >> M;

    for(int i = 0; i < N; i++) {
        cin >> arr[i];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}