2792 보석상자

이분탐색 문제는 항상 기발하게 어려운 것 같다. 이분탐색 문제들 좀 풀면서 감이 생겼나 싶었는데 이 문제도 역시나 어려웠다. 

 

또 계속 고민하다가 풀렸다...!!

어떻게 이 생각이 떠올랐나 물으면 답은 못하겠다. 그냥 감.. 감으로 풀었다. 

 

질투심이 가장 클 때와 작을때를 범위로 잡고 그 때의 인원 수를 확인해서 참인지 거짓인지 판단한다. 

 

어려웠던 건 범위.. 범위 잡는게 묘하게 어렵다. 그래서 이것도 막 해보다가 3번처럼 해야 한다는 걸 깨달았다. 음.. 왜 저렇게 되는지를 잘 모르겠다. 처음에 [1, 8)로 하면 안 되고.. (0, 7]로 하니 답이 나온다.. 음..   왜.. 음.. 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;

bool check(i64 mid, int n, vector<int> v){
    i64 c = 0;
    for(int i = 0; i < v.size(); i++)
        c += (v[i] + mid - 1) / mid;
    if(c <= n)
        return true;
    return false;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> v(m);
    
    for(int i = 0; i < m; i++){
        scanf("%d", &v[i]);
    }
    
    int low = 0;
    i64 high = *max_element(v.begin(), v.end());
    
    while(true){
        if(low + 1 == high)
            break;
        i64 mid = (low + high) / 2;
        
        if(check(mid, n, v))
            high = mid;
        else
            low = mid;
    }
    printf("%lld", high);
    
    return 0;
}

 

맞았긴 맞았다