[구름LEVEL] 선별진료소

난이도	정답률
★★★	-%

프리미엄 알고리즘 위클리 비타알고 시즌3 4월 1주차

goorm

문제

 

해결

key point, N명의 사람을 진료하기 위해 걸리는 최소 시간을 이분탐색하자!

1. k개의 진료실에서 환자를 진료하기 위해 걸리는 시간이 각각 주어진다. → a[k]
2. 그리고 진료실에서 걸리는 시간을 가지고 전체 시간을 알아내야한다.
3. 하지만 우리는 거꾸로, 임의의 시간이 걸린다고 가정하고 몇 명을 치료할 수 있는지 구할 것이다.
   1. 각 진료실에서 치료할 수 있는 환자의 수는 (전체 시간)/a[k] 이다.
4. 임의의 시간에서 각 진료실에서 치료할 수 있는 환자의 수를 모두 더한 값이 N보다 크거나 같다면 최소 시간을 구해야 하므로 더 작은 시간 내에서 N명 이상의 환자를 치료할 수 있는지 탐색해봐야한다.
5. 그래서 우리는 최소와 최대를 각각 l(left)과 r(right)로 잡고 이분탐색을 진행해서
6. 해당 시간에 진료할 수 있는 환자의 수를 매번 구해서 N과 비교했다.
7. 해당 시간에 진료할 수 있는 환자의 수는 해당시간을 진료소에서 걸리는 시간으로 나눈 값이기 때문에 최대 10억이 될 수 있고, k개의 진료실이 있어서 10억*k가 될 수 있어 int형의 범위를 넘어서기 때문에 long long 형으로 지정해주었다.
8. 반복문을 계속 돌다가 l이 r과 같거나 더 커지는 상황이 되면 종료한다.

코드

#include <cstdio>
using namespace std;
typedef long long ll;
int n, k, ans, arr[100005];
ll chk(int mid) {
    ll res = 0;
    for (int i = 0; i < k; i++) {
        res += (mid / arr[i]);
    }
    return res;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < k; i++) {
        scanf("%d", &arr[i]);
    }
    int l = 0, r = 1e9;
    while (l <= r) {
        int mid = (l + r) / 2;
        ll res = chk(mid);
        if (res >= n) {
            r = mid - 1;
            ans = mid;
        }
        else l = mid + 1;
    }
    printf("%d", ans);
    return 0;
}