큰돌님 강의의 첫번째 이분탐색 문제인 c++ 보석상자 이다.
나는 자료구조에서의 이분탐색을 제외하고 알고리즘 이분탐색은 왜 이분탐색을 하는지 몰랐다.
물론 지금도 완벽하게 마스터한건 아니지만 한번 이해하고 나니 조금 쉽다.
내 글을 볼수도 있는 사람들에게 도움이 되길 바라며 내가 이해한것을 작성하려합니다.
조건
현재 M가지 다른 보석을 N명의 학생들에게 나눠줘야한다.
질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수라 한다.
만약 빨간 보석이 4개 파란보석이 7개이면 각자의 조건에 맞게 질투심이 3이 된다.
내가 생각한 방법
나는 2개의 보석일때만 생각했다. 너무 1차원적인 방법이다.
그래서 5명임으로 (1,4),(2,3),(3,2),(4,1) 로 나누어서 각자의 결과에 최대의 수 중 최소를 고르려고 했다.
하지만 N의 범위는 0<= x <=10억이다.
그러면 한번 돌때마다 10억번 도는것이다.
1억연산에 1초라 가정하면 한번도는데도 벌써 10초가 걸리는것이다.
그렇기에 10억연산에 대해 1초안에 돌아가는 알고리즘을 짜야하는것이다.
이해
이분탐색에서 가장 중요한것은 "기준" 이다.
그리고 이문제에 이분 탐색을 하기 위한 기준은 "보석을 고르는 개수" 이다.
그리고 이 보석을 고르는 개수가 최소가 되면 그것이 답이다.
최소일때와 최대일때의 각각 기준을 생각해본다.
2개의 색상이 있는 보석에 대해 각각 7 ,4 개 가 들어있다면 각각 보석 수에 대해 몇명씩 고를수 있는지 생각해보자.
최소일떄는 1개고를수 있을때 7개 보석에서의 7개를 고를수있고 4개 보석에서의 4개를 고를수있어서 총 11명에게 나눠줄수있다.
그리고 최악일땐 보석들중 최대값인 7을 생각해보면 첫번쨰에서 7개 두번쨰에서 7개를 고르면 2명에게 나눠줄수있다.
이말은 고를수있는 보석이 작아지면 나눠줄수있는 사람의 수가 많아지고 반대로 보석이 커지면 나눠줄수있는 사람의 수가 적어진다.
그렇기에 이것을 사용해서 이분탐색을 하면된다.
최소인 1 과 최대인 7의 중간값인 4를 사용해서 몇명에게 나눠줄수 있는지 확인하고, 그 값으로 확인한 나눠줄수있는 사람의 수가 작으면 더 늘려줘야기에 고를수있는 보석을 더 줄이고 반대로 나눠줄수있는 살마의 수가 많으면 더 줄여줘야기에 고를수있는 보석을 더 늘린다. 그렇게 최소의 값을 찾는것이 답이된다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N,M;
int min_N=1,max_N=-987654321,data_N,temp,mid;
int ret;
vector<int> v;
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 >> data_N;
max_N=max(data_N,max_N);
v.push_back(data_N);
}
while(min_N<=max_N) {
mid=(min_N+max_N)/2;
temp=0;
for(int a:v) {
if(a%mid)
temp+=(a/mid)+1;
else
temp+=(a/mid);
}
if(temp<=N) {
ret=mid;
max_N=mid-1;
}
else {
min_N=mid+1;
}
}
cout << ret << "\n";
return 0;
}
temp 는 나눠줄수 있는 사람수이고
min_N 과 max_N을 줄이고 늘림으로써 최적의 값을 찾아 나가면 된다.
