[C++][BOJ] 2792번 보석 상자(feat. 이분 탐색)

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

 

아이들의 수와 보석 색상의 수, 보석의 개수가 주어진다.

모든 보석을 나누어줄 때 최대한 차이가 나지 않게 나누어주는 방법을 구하는 문제이다. 한 아이가 갖는 보석의 수를 질투심이라 표현했다.

이 때 한 아이는 같은 보석의 색상만 가져야 한다. 또한, 보석을 못받는 아이는 있어도 남는 보석은 없어야 한다.

 

[입력]

첫째 줄에 아이들의 수 N과 색상의 수 M이 주어진다. (1 ≤ N ≤ 109, 1 ≤ M ≤ 300,000, M ≤ N)

다음 M개 줄에는 구간 [1, 10^9]에 포함되는 양의 정수가 하나씩 주어진다. K번째 줄에 주어지는 숫자는 K번 색상 보석의 개수이다.

[출력]

첫째 줄에 질투심의 최솟값을 출력한다.

 

 

[풀이]

하나의 보석의 수가 최대 10^9 가 주어지므로 단순 완전탐색으로는 풀 수 없다.

이렇게 큰 수가 주어지고 최소의 경우를 찾는 경우에 '이분탐색' 알고리즘을 이용한다.

 

이 문제에서 이분탐색을 적용하는 법은 질투심이 가질 수 있는 최소 수와 최대수를 한정하고 중간값부터 탐색하며 최소 질투심을 찾는 것이다.

 

예제 1을 봐보자.

5 2
7
4

아이들의 수: 5, 보석 색깔 2

보석 색깔 1의 개수: 7

보석 색깔 2의 개수: 4

 

이 때, 최소 질투심은 1, 최대 질투심은 7이라고 생각해볼 수 있다.

최대 질투심이 7인 이유는 한 아이는 반드시 같은 색깔의 보석만 가질 수 있으므로 한 아이가 가질 수 있는 최대 보석의 개수는 보석 색깔1의 7이기 때문이다.

 

따라서 1 ~ 7을 이분탐색하며 최소 질투심을 찾는다.

(참고로 이분탐색은 중간값부터 탐색하고 정답이 중간값을 기준으로 왼쪽에 있는지, 오른쪽에 있는지 Up & Down 게임을 하는 것이다. 1~7의 중간값은 '(최소값 + 최대값) / 2' 수학 공식으로 구할 수 있다.)

 

1) 질투심을 4 라고 가정하고 보석을 나눠보자. (1+7) / 2 = 4

3명에게 나눠줄 수 있다. 5명보다 적으므로 더 세세하게 쪼갤 수 있다는 것을 알 수 있다. 더 작은 질투심 지수를 찾기 위해 최대값을 '중간값 -1' 로 갱신하고 다시 찾아보자.

 

2) 최소값 2, 최대값 3 => 중간값 2(질투심을 2) 로 두고 보석을 나눠보자.

5개 이상으로 쪼개지므로 '보석 나누기 > 아이들 수' 가 되므로 보석이 남아서 안된다. 더 큰 값으로 나눠야 하므로 최소값을 '중간값 +1' 로 갱신하고 탐색해보자.

 

3) 최소값 2, 최대값 3 => 중간값 2(질투심을 2) 로 두고 보석을 나눠보자.

2번과 동일한 경우이므로 최소값 = 중간값 + 1 로 갱신하고 다시 탐색해보자.

 

4) 최소값 3, 최대값 3 => 중간값 3 (질투심 3)

5명에게 나눠줄 수 있다. 또한 '최소값 = 최대값' 이므로 더이상 이분탐색을 진행할 수 없다. 따라서 최소 질투심 지수는 3이다.

 

이렇게 질투심 값을 중간값으로 정해두고 Up & Down 하며 최소 질투심을 찾으면 된다. 시간복잡도는 O(logN) !

 

 

[코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int childrenNum, colorNum, input;
int minNum = 1, maxNum = 0;
vector<int> colors;

int GetJealousy();

int main() {

	cin >> childrenNum >> colorNum;
	for (int i = 0; i < colorNum; i++) {
		cin >> input;
		colors.push_back(input);
		maxNum = max(maxNum, input);
	}

	cout << GetJealousy() << "\n";

	return 0;
}

int GetJealousy() {
	int jealousy = 0;

	while (minNum <= maxNum) {
		int mid = (minNum + maxNum) / 2;
		int divideNum = 0;

		for (int color : colors) {
			if (color % mid) divideNum += (color / mid) + 1;
			else divideNum += (color / mid);
		}

		if (divideNum <= childrenNum) {
			jealousy = mid;
			maxNum = mid - 1;
		}
		else minNum = mid + 1;
	}
	return jealousy;
}