[BOJ] 백준 2613. 숫자 구슬 (Gold II)

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

2613번: 숫자구슬

2004 KOI 지역본선 고등부 4번 문제이다.

원래 고등부 문제들은 대체로 플레, 다이아이나, 지역본선이라 그런지 크게 어렵지 않은 문제였다.

다만, 난 이 문제를 좀 오래 헤맸다.

---

의식의 흐름 및 해설

흔히 볼 수 있는 결정 문제이다.

최댓값이 k일 때, M개 그룹으로 나누어서 진행할 수 있는가? 와 같이 결정을 묻는 문제는 파라메트릭 서치를 주로 이용한다.

사실 dp 생각도 했는데, dp 탑다운으로 코드를 짠 후 백트래킹으로 역추적을 해야할 것처럼 보였다. 결정 문제니까 이분탐색을 이용하여 해결해보고 dp를 필요하면 사용해보려 했으나, 다행히 이분탐색과 약간의 구현만으로 충분히 해결이 가능했다. 다만, 구현이 이분탐색 구현보다 훨씬 까다로운 문제였다.

 

우선, 각 그룹에 숫자 구슬 최소 1개는 포함돼야 하므로 이분탐색 범위의 최솟값은 숫자구슬 값의 최댓값으로 해야 한다. 그렇지 않으면, 그룹 내에 가장 큰 숫자구슬은 포함되지 못하는 경우가 발생한다. 최댓값은 INF로 진행하였다.

 

그룹의 최댓값이 mid일 때, 그룹을 M개 이하로 만들 수 있으면 true를 리턴하고 아닐 경우 false를 리턴하게 하였다.

또한, 마지막 그룹은 for문이 끝날 때까지 정산되지 않으므로 반복문 이후에 따로 정산해주도록 한다. 만약, 마지막 그룹의 합이 mid를 넘는다면 그룹 수를 INF로 만들어 불가능한 그룹으로 만들었다.

bool check(int n) {
	int ret = 0, p = 0, cnt = 0;
	for (int i = 0; i < N; i++) {
		if (ret + a[i] > n) {
			p++;
			cnt = 1;
			ret = a[i];
		}
		else {
			ret += a[i];
			cnt++;
		}
	}
	if (ret && ret <= n)
		p++;
	else
		p = INF;
	if (p <= M)
		return true;
	return false;
}

또한, 이분탐색으로 답을 구한 후에,

정답 케이스를 적절하게 M개의 그룹으로 나누어야 한다. 

위에서 구한 bool 함수는 M개 이하로 만들 수 있는지 여부이므로, 정확히 M개의 그룹으로 나뉘지 않을 확률이 존재하기 때문이다.

	solve(s, INF);
	cout << ans << "\n";
	int ret = 0, p = 0, cnt = 0;
	for (int i = 0; i < N; i++) {
		if (ret + a[i] > ans || N - i == M - p - 1) {
			cout << cnt << " ";
			cnt = 1;
			p++;
			ret = a[i];
		}
		else {
			ret += a[i];
			cnt++;
		}
	}

따라서 처음엔 그룹의 합이 ans를 넘지 않을 때까지 그룹을 만들다가,

남은 숫자구슬의 개수와 만들어야 하는 그룹의 개수가 같을 때는 그냥 1개씩 넣도록 하였다.

맨 마지막은 반복문에서 정산이 안되는 것에 주의하자!

 

아래 테스트케이스를 참고하자.

 

6 4
1 1 1 4 1 1
ans:
4
1 2 1 2
------------
4
2 1 1 2
------------
4
3 1 1 1

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int MAX = 301;
const int INF = 0x3fffffff;
int N, M, a[MAX], ans = INF;
vector<int> res;
bool check(int n) {
	int ret = 0, p = 0, cnt = 0;
	for (int i = 0; i < N; i++) {
		if (ret + a[i] > n) {
			p++;
			cnt = 1;
			ret = a[i];
		}
		else {
			ret += a[i];
			cnt++;
		}
	}
	if (ret && ret <= n)
		p++;
	else
		p = INF;
	if (p <= M)
		return true;
	return false;
}
void solve(int s, int e) {
	while (s <= e) {
		int mid = (s + e) / 2;
		if (check(mid)) {
			ans = min(ans, mid);
			e = mid - 1;
		}
		else
			s = mid + 1;
	}
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	int s = 0;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		s = max(s, a[i]);
	}
	solve(s, INF);
	cout << ans << "\n";
	int ret = 0, p = 0, cnt = 0;
	for (int i = 0; i < N; i++) {
		if (ret + a[i] > ans || N - i == M - p - 1) {
			cout << cnt << " ";
			cnt = 1;
			p++;
			ret = a[i];
		}
		else {
			ret += a[i];
			cnt++;
		}
	}
	cout << cnt << "\n";
}

0x3fffffff의 값은 약 10억 7천만 0x3f3f3f3f의 값이 약 10억 6천만으로, memset으로도 INF로 적용이 가능하므로 굉장히 편리했다. (이번 문제에선 이용되지 않음.) 0x3fffffff는 이상하게 memset으로 하면 이차원배열일 때 모든 값이 -1로 저장됐다.

---

오랜만에 이분탐색 문제를 풀었다.

이 문제를 풀면서 결정 문제에 따른 이분탐색 감을 살려서 좋은 듯하다.