[Programmers] 입국심사 (C++)

문제

n명이 줄을 서 있다.

각 입국 심사대마다 소요되는 시간은 다르다.

한 심사대는 한 명만 심사할 수 있다.

모든 사람이 심사 받는데 걸리는 시간의 최솟값 구하기

생각할 것

1. 가장 먼저 심사시간 정렬하기
2. 심사시간의 범위 : 1 ~ 가장 오래걸리는 사람 * 모든 사람 수
3. mid 시간 동안 심사할 수 있는 사람의 수를 찾기!

반례

입력값 〉	1000000000, [1, 1000000000]
기댓값 〉	1000000000

틀렸던 이유 : 자료형의 범위 때문에 while문이 실행되지 않았다.

잘못된 코드

long long end = times[times.size() - 1] * n;

고친 코드

long long end = (long long)times[times.size() - 1] * n;

코드

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    long long start = 1;
    long long end = (long long)times[times.size() - 1] * n;
    long long mid, people;

    sort(times.begin(), times.end());
    while(start <= end) {
        mid = (start + end) / 2;
        people = 0;
        for(int i = 0; i < times.size(); i++) { // mid 시간 동안 심사할 수 있는 모든 사람의 수
            people += (mid / times[i]);
        }

        if(people >= n) { // 너무 많은 사람 심사 가능하거나, 딱 맞는 경우
            answer = mid;
            end = mid - 1;
        }
        else { // 너무 적은 사람 심사 가능한 경우
            start = mid + 1;
        }
    }

    return answer;
}