이번에는 백준 2792번 보석 상자 문제를 풀어보았습니다.
문제를 처음 봤을 때 질투심의 최솟값을 직접 구하기는 어렵다고 생각했습니다.
하지만 질투심을 하나의 값으로 정해두었을 때, 모든 보석을 나누어 줄 수 있는지는 쉽게 판단할 수 있다는 점을 이용하여 이분 탐색으로 해결하였습니다.
문제 설명
보석은 색깔별로 개수가 주어집니다.
한 학생은 하나의 색깔만 받을 수 있으며, 가장 많은 보석을 받은 학생의 보석 개수를 질투심이라고 합니다.
질투심이 최소가 되도록 보석을 나누어 줄 때의 질투심을 구하는 문제입니다.
풀이 아이디어
질투심을 X라고 가정해보았습니다.
그러면 한 학생이 최대 X개까지만 받을 수 있습니다.
각 색깔의 보석 개수를 X개씩 나누었을 때 필요한 학생 수를 계산하면, 현재 질투심으로 모든 보석을 나누어 줄 수 있는지 확인할 수 있습니다.
- 필요한 학생 수가 N명 이하라면 가능한 경우입니다.
- 필요한 학생 수가 N명을 초과한다면 질투심이 너무 작은 경우입니다.
이 성질을 이용하여 질투심을 이분 탐색하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N,M;
int jewel[300000];
int l = 1, r, m;
int result = INT_MAX;
bool search(int num) {
int ret = 0;
for (int i=0; i<M; i++) {
ret += jewel[i] / num;
if (jewel[i] % num)
ret++;
}
return ret <= N;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
for (int i=0; i<M; i++) {
cin >> jewel[i];
r = max(r, jewel[i]);
}
while(l <= r) {
m = (l + r) / 2;
if (search(m)) {
result = min(result, m);
r = m - 1;
}
else {
l = m + 1;
}
}
cout << result << '\n';
return 0;
}풀이 흐름
- 질투심의 탐색 범위를 설정합니다.
- 현재 질투심으로 모든 보석을 나누어 줄 수 있는지 확인합니다.
- 가능한 경우 더 작은 질투심을 탐색합니다.
- 불가능한 경우 질투심을 증가시킵니다.
- 이분 탐색이 끝나면 최소 질투심을 출력합니다.
구현 포인트
1. 이분 탐색 범위 설정
질투심은 최소 1개, 최대 가장 많은 보석 개수입니다.
int l = 1;
int r = 가장 많은 보석 개수;가장 많은 보석 개수는 입력을 받으면서 갱신하였습니다.
r = max(r, jewel[i]);2. 현재 질투심으로 가능한지 확인
현재 질투심을 num이라고 할 때 필요한 학생 수를 계산하였습니다.
ret += jewel[i] / num;
if (jewel[i] % num)
ret++;즉,
ceil(보석 개수 / 질투심)을 직접 구현한 것입니다.
모든 색깔에 대해 필요한 학생 수를 계산하였습니다.
3. 가능한 경우
필요한 학생 수가 현재 학생 수 이하라면 가능한 경우입니다.
if (search(m)) {
result = min(result, m);
r = m - 1;
}현재 값보다 더 작은 질투심도 가능한지 확인하기 위해 왼쪽 구간을 탐색하였습니다.
4. 불가능한 경우
필요한 학생 수가 학생 수를 초과한다면 질투심이 너무 작은 경우입니다.
else {
l = m + 1;
}따라서 질투심을 증가시켜 다시 탐색하였습니다.
5. 최소 질투심 탐색
이 문제의 핵심은
질투심이 커질수록 필요한 학생 수는 줄어든다.
는 단조성이 존재한다는 점입니다.
따라서 가능한 질투심의 최솟값을 이분 탐색으로 효율적으로 구할 수 있었습니다.
