🌞문제

🌞접근법

조건1. n명이 입국심사를 위해 줄을 서서 기다리고 있다.
조건2. 각 입국 심사대에 있는 심사관마다 심사하는데 걸리는 시간이 다르다.
조건3. 처음에 모든 심사대는 비어 있다.
조건4. 한 심사대에서는 한 명만 심사를 할 수 있다.
조건5. 가장 앞에 서있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있도 있고, 잠시 기다렸다가 다른 심사대로 갈 수도있다.
조건6. n은 1~10억
조건7. 심사관 한명이 심사하는데 걸리는 시간은 1분~10억분
조건8. 심사관은 1~10만명

결과 값 : 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하는 방법은?

걸리는 시간이 최소가 되려면,

각 심사관은 독립적으로 일을 끝내고 다시 시작한다.
따라서 각 심사관이 일을 마치는 시간을 누적으로 저장하는 배열을 만들어준다.
그리고 sort를 통해서 오름차순으로 정렬해준다.
여기서 가장 좋은 경우는 맨 앞에 있는 요소를 선택하는 경우이다.
그렇기 때문에 해당 값을 return 값에 더해준다.
이를 n번만큼 반복한다.

위의 방법으로 풀게되면 시간초과가 발생한다.

그래서 할 수 있는 다른 방법은 전체 누적시간을 이분 탐색을 하는 방법이다.
즉 정답을 추정하고 그 정답이 최선의 답인지를 판단하는 것이다.

일단 답을 추정하기 위해서는 답의 범위를 정의해야한다.
여기서 답은 최악의 경우 첫번째 심사관이 모든 사람들을 심사하는 것이다.
이 경우는 n*times[times.size()-1] 로 구할 수 있다.

그렇게해서 결과 값을 구했으면 이 정답의 가운데를 선택하여 그 가운데 값이
n보다 작은지, 큰지, 또는 같은지를 확인 해준다.

그리고 나서 그 결과에 따라 right, left 값의 조정을 통하여 mid값을 변경을 해준다.

이 반복을 left ~ right의 범위에 속하는 숫자가 없을 떄까지 반복을 한다.
이 경우는 right > left인 경우이다.

🌞풀이

#include<iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;


long long solution(int n, vector<int> times) {
    
    long long answer;
    sort(times.begin(),times.end());
    
    long long left = (long long)times[0], right = (long long)times[times.size()-1] * n;
    answer = right;

    while (left <= right) {
        long long sum = 0;
        long long mid = (left + right) / 2;
        for (int i = 0; i < times.size(); i++) {
            sum += mid / times[i];
        }
        if (sum >= n) {
            if(answer > mid)
                answer = mid;
            right = mid - 1;

        }
        else {
            left = mid + 1;
        }
    }

    return answer;
}