C++ / 프로그래머스 / 입국심사

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

문제풀이

선입 선출 스케줄링 문제를 풀고 나니까 쉬웠다. 똑같이 파라메트릭 서치로 풀면 된다.

선입 선출 스케줄링에서는 작업을 시작하는 부분을 구해야 했지만, 이 문제는 끝나는 부분을 구하면 된다.

주의할 점은 범위이다, 최대범위가 1,000,000,000 * 1,000,000,000이므로 long long형을 쓴다.

문제에 있는 예시를 보자. n = 6, times = [7, 10], answer = 28

7분이 걸리는 심사대에 4명, 10분이 걸리는 심사대에 2명이 가야 한다.

7*4 = 28, 10*2 = 20 이렇게 해서 답이 28이 나온 것이다.

나눗셈을 하고 몫을 더해서 n이 되는 값을 구하는 것이다.

 

        if (cnt < n) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }

만약 cnt가 n이라면 left와 right 범위 안에 답이 있다는 뜻이다.

최솟값을 구해야 하므로 right를 움직여야 한다.

right를 움직이다 정답을 지나칠 수 있으므로 while의 조건을 left <= right로 잡았고, left를 return 했다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#define MAX 1000000000000000000
using namespace std;

long long solution(int n, vector<int> times) {
    long long left(0), right(MAX), mid(0), idx(0), cnt(0);

    while (left <= right) {
        mid = (left + right) / 2;
        cnt = 0;
        for (idx = 0; idx < times.size(); ++idx) {
            cnt += mid / times[idx];
        }        
        if (cnt < n) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return left;
}