[알고리즘] 백준 2792번: 보석 상자 (C++), 최솟값과 최댓값의 활용

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

2792번: 보석 상자

문제에서 요구하는 질투심의 최솟값을 알아내기 위해 이분 탐색으로 질투심의 최솟값을 도출할 수 있는 방법이 떠오르지 않아서 '다른 값을 도출해야 하나'라고 생각했다.

 

나에게는 기존에 항상 이분 탐색에서 썼던 틀(?) 같은 게 있었다.

while (low <= high) {
	int mid = (low + high) / 2;
    
	if (조건식) {
		high = mid - 1;
		answer = mid
	}
	else {
		low = mid + 1;
	}
}

 

이번 문제에서는 이 틀의 영역을 조금 확장시킨다.

---

솔루션

(+참고 https://jaimemin.tistory.com/1128)

 

중요한 건 이분 탐색에서 어떤 값을 찾으며 두 번 나누어갈 때 어떠한 조건이 필요한지 먼저 파악을 할 수 있어야 한다. 찾아야 하는 값은 '질투심의 최솟값'이며 조건은 '주어진 mid 값으로 n명에게 전부 나누어 줄 수 있는가?' 

n명 이상 나누어줄 수 없다면 더 큰 값으로 가서 더 큰 값으로는 나눠줄 수 있는지 파악해야 한다. 즉, 나누어줄 수 있는 값 중 최솟값이 되어야 하는 것이다.

 

참고한 코드에서는 조금 헷갈리는 부분이 있었다.

다음 내용을 확실히 숙지한 상태에서 봐야 한다.

mid 값(나누는 값)이 작아질수록 나눠갖는 사람은 많다.
나누어 갖는 사람이 n명보다 작다면 mid값을 줄여야 한다.

 

[주어진 mid값으로 나누어 줄 수 있는 n명을 count 하는 함수]

여기서 리턴하는 값이 나누어줄 수 있는 사람(cnt)이 n명 이하라면 TRUE(1) 임을 리턴한다.

bool judge(int mid) { // 이 중간값으로 나누어줄 수 있는가
	// 
	int cnt = 0;
	if (mid == 0) { // error: division by zero
		return 0;
	}
	for (int i = 0; i < m; i++) {
		cnt += jam[i] / mid;
		if (jam[i] % mid) {
			cnt++;
		}
	}

	// n명 이상 나누어 줄 수 있는가
	// >> 이상으로 나누어주면 이분탐색에서 최대한 많은 사람에게
	// 나누어주려하기 때문에 결과값이 도출 될 수 없다.
	return n >= cnt;
}

---

[전체 소스 코드]

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

int n, m;
int jam[300000];

bool judge(int mid) { // 이 중간값으로 나누어줄 수 있는가
	// 
	int cnt = 0;
	if (mid == 0) { // error: division by zero
		return 0;
	}
	for (int i = 0; i < m; i++) {
		cnt += jam[i] / mid;
		if (jam[i] % mid) {
			cnt++;
		}
	}

	// n명 이상 나누어 줄 수 있는가
	// >> 이상으로 나누어주면 이분탐색에서 최대한 많은 사람에게
	// 나누어주려하기 때문에 결과값이 도출 될 수 없다.
	return n >= cnt;
}

int main() {
	cin >> n >> m;
	
	int idx;
	int high = 0;
	for (int i = 0; i < m; i++) {
		cin >> idx;
		jam[i] = idx;
		high = max(high, idx);
	}

	int low = 0;
	int answer = INT_MAX;

	while (low <= high) {
		int mid = (low + high) / 2;

		if (judge(mid)) {
			high = mid - 1;
			// 여기서의 min 함수는 질투심의 최솟값이 아니다.
			// 최솟값을 answer에 넣는다는 것은 judge함수에서 n == cnt가
			// 되는 경우를 뜻한다.
			answer = min(answer, mid);
		}
		else {
			// mid 값이 작으면 더 많은 사람에 나누어 줄 수 있다.
			// >> 더 큰 값을 줘서 n명 이하로 나누어 줄 수 있게 해야 함
			low = mid + 1;
		}
	}

	cout << answer;
	return 0;
}

---

업 솔빙이 필요한 문제

지금 당장에 이해는 갔지만 시간을 두고, 다시 풀어서 접근할 수 있는지 봐야겠다.