BOJ-2613 숫자구슬

필요한 지식

1. 이분탐색

접근

1. 이분탐색의 mid값을 한 그룹의 최대 숫자의 합으로 두고 이분탐색을 진행한다.

2. mid값을 정하고 그 값으로 구슬이 저장된 벡터를 돌면서 mid값을 넘지않게 그룹으로 나누었을때 몇개의 그룹으로 나뉘는지 체크한다.

3. 정확히 m개의 그룹으로 나뉘었거나, m개보다 적은 수의 그룹이 형성되었다면 right값을 mid-1로 줄여준다. 정확히 m개의 그룹으로 나뉘었다면 각 그룹의 최대값을 갱신해준다.

4. m개보다 많은 수의 그룹이 형성되었다면 left값을 mid+1로 늘려서 다시 과정을 반복한다.

5. 접근 2번에서 mid값을 넘지않게 라고 했지만 현재 선택한 그룹에 하나도 선택되지않았을 경우에는 mid값을 넘더라도 넣어주고 다음 그룹으로 넘어가야한다. 그렇지않으면 아래와 같은 반례가 존재하게된다.

4 4
3 1 1 1

//정답
3
1 1 1 1

코드(C++)

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
using namespace std;
vector<int>v;
int ans = INT_MAX, ansmid = 0;
int main() {
	//input
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int x; cin >> x; v.push_back(x);
	}
	//binary search
	int l = 0, r = INT_MAX;
	while (l < r) {
		int mid = (l + r) / 2;
		int tans = 0, tmp = 0, cnt = 0;
		for (auto it : v) {
			//tmp+it이 mid를 넘을떄
			if (tmp + it > mid) {
				bool flag = false;
				if (tmp == 0) {
					flag = true;
					tmp = it;
				}
				cnt++;
				tans = max(tans, tmp);
				tmp = 0;
				if (flag)continue;
				else tmp += it;
			}
			//넘지 않을때
			else tmp += it;
		}
		if (tans != 0) {
			tans = max(tans, tmp);
			cnt++;
		}
		if (cnt > m) {
			l = mid + 1;
		}
		else {
			if (cnt == m) {
				ans = min(ans, tans);
				if (ans == tans)ansmid = mid;
			}
			r = mid - 1;
		}
	}
	//output
	cout << ans << "\n";
	int tmp = 0, cnt = 0;
	for (auto it : v) {
		if (tmp + it > ansmid) {
			if (tmp == 0) {
				cout << 1 << " ";
			}
			else {
				cout << cnt << " ";
				tmp = cnt = 0;
				tmp += it;
				cnt++;
			}
		}
		else {
		tmp += it; cnt++;
		}
	}
	if(cnt!=0) cout << cnt;
	return 0;
}

• 처음에 접근5번을 고려해주지 않아 많이 해맸고, 접근5번 때문에 코드가 많이 더러워졌다.