문제

문제 링크

해설

• 질투심 = 가장 많은 보석을 가져간 학생이 가진 보석갯수
• 최대 아이들의 수는 10억이기 때문에 이 문제는 일반적인 O(N)~O(N²) 방법으로는 시간 내에 해결할 수 없다는 것을 알 수 있습니다.
• 따라서, 질투심이 mid일 때, N명의 학생에게 보석을 나눠줄 수 있는지 여부를 검사하는 방법을 사용합니다.
• 즉, 이분탐색을 이용해 최적화 문제를 mid일 때 가능해? 불가능해? 라는 식의 결정문제로 바꿔 최적해를 더욱 빠르게 찾는 방법입니다.
• low는 0으로, 입력받는 M개의 보석 정보들 중 가장 최대치를 high로 초기화합니다.
• 중앙값인 mid를 계산한 뒤, M개의 보석을 N명에게 나눠줄 수 있는지 여부를 검사합니다.
  • for (int i = 0; i < M; ++i) { } 반복문을 돌면서 i번째 보석을 mid로 나눈 몫만큼의 학생들에게 나눠줍니다.
  • 나눠준 학생이 N보다 작거나 같다면, mid가 너무 큰 것이니 high = mid - 1로 줄여야 하고,
  • 나눠준 학생이 N보다 크다면, mid가 너무 작은 것이니 low = mid + 1로 늘려야 합니다.

코드

#include<bits/stdc++.h> 
using namespace std;  
using ll = long long;

ll N, M, a[300'002], ans;

bool isAvailable(ll mid) {
    ll num = 0; 
    for(int i = 0; i < M; i++) {
        num += a[i] / mid;
        if (a[i] % mid) num++; 
    }
    return N >= num; 
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> N >> M;
    
    ll lo = 1, hi = 0, mid;
    for(int i = 0; i < M; i++) cin >> a[i], hi = max(hi, a[i]);
    
    while (lo <= hi) {
        mid = (lo + hi) / 2;
        if (isAvailable(mid)) ans = mid, hi = mid - 1;
        else lo = mid + 1;
    }
    cout << ans;
} 

소스코드 링크

• 안전하게 long long 자료형을 사용하는 것이 좋습니다.

결과