[프로그래머스] Lv.3 입국 심사(이진 탐색), [백준] 3079번 입국심사 - C++

Lv.3 입국 심사

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

n	times	return
6	[7, 10]	28

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

---

문제 요약 :

각 심사관마다 심사하는 시간이 times로 주어졌을 때 n명의 사람이 심사를 받는 총 시간 구하기

생각할 점:

이진 탐색을 사용

• 입국 심사 시간 벡터를 오름차순으로 정렬한다.
• 최소 시간, 제일 오래걸리는 시간으로 초기화해서 시간들을 이진 탐색
  • 심사대의 수 : times.size()
  • 가장 적게 걸리는 시간 → 사람수가 1이고 심사 시간이 1인 경우 → 1
  • 제일 오래걸리는 시간? → 가장 오래걸리는 검색대 * n명인 경우
  • times 벡터의 가장 마지막 심사대의 시간이 가장 오래걸리는 검색대이다.
• mid 시간 동안 통과할 수 있는 사람의 수를 passed에 저장해서
• passed(mid 시간동안 처리할 수 있는 사람수)가 n보다 작으면 조건을 만족하지 못하니까 최소의 범위를 늘려서 탐색범위를 이동

(mid 시간 안에 n명을 심사할 수 없다 → 시간을 늘려줘야함)

• passed가 n보다 크면 mid 가 답이 될 수 있으므로 answer에 넣어주고 최대의 범위를 더 좁혀서 최소값을 찾을 수 있는 탐색 범위로 이동 (mid 시간 안에 n명 심사가 가능하다 → 답이 mid 이거나 mid보다 작은 시간이다)
  

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(),times.end());
    
    long long min = 1;
    long long max = (long long) times[times.size()-1] * n;
    
    while(min <= max){
        long long mid = (min + max)/2;
        //mid 시간동안 통과한 사람의 수
        long long passed = 0;
        for(int i =0; i < times.size(); i++){
            //mid 시간을 심사한 시간들로 나눈 값을 더하면 통과한 사람 수
            passed += (mid / times[i]);
        }
        if(passed < n){
            min = mid+1;
        }
        else{
            answer = mid;
            max = mid-1;
        }
    }
    
    return answer;
}

코드 설명

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

using namespace std;

long long solution(int n, vector<int> times) {

    long long answer = 0;

		//심사하는 시간들을 오름차순 정렬
    sort(times.begin(),times.end());

    //총 심사하는 데 가장 적게 걸리는 시간( 1명 * 심사대 소요 시간 1)
    long long min = 1;

		//가장 오래 걸리는 시간 ( 벡터의 가장 마지막 심사대의 시간 * 전체 인원)
		//전체 인원이 가장 오래 걸리는 심사대에서 심사를 받는 게 가장 오래걸린다.
    long long max = (long long) times[times.size()-1] * n;

    //이진 탐색
    while(min <= max){
				//mid = 이진 탐색을 위한 가장 중간 값(소요되는 가장 중간 시간)
        long long mid = (min + max)/2;

        //mid 시간동안 통과한 사람의 수
        long long passed = 0;

        for(int i =0; i < times.size(); i++){
            //mid 시간을 심사한 시간들로 나눈 값들을 더하면 통과한 사람 수
            passed += (mid / times[i]);
        }

				//mid 시간동안 통과한 사람의 수가 찾고 있는 n보다 작다면
				//탐색 범위가 잘못 된 경우-> mid 시간 동안 n명을 심사할 수 없다.
        if(passed < n){
					// 탐색 시간을 늘려줘야함
            min = mid+1;
        }
				//n명 이상이 심사 받은 경우 mid 시간 안에 n명의 심사가 가능하다.
				//즉 답이 mid이거나 mid 보다 적은 값이다.
        else{
            answer = mid;
            max = mid-1;
        }
    }
    
    return answer;
}

같은 문제

백준에서 찾은 동일한 문제
백준 3079번: 입국심사

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    int N;
    long long M;
    long long answer = 0;
    vector<int> T;
    
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        int x;
        cin >> x;
        T.push_back(x);
    }
    
    sort(T.begin(), T.end());
    
    long long min = 1;
    long long max = T[N-1]* M;
    
    while(min <= max) {
        long long mid = (min + max) / 2;
        long long passed = 0;
        for(int i = 0; i < N; i++) {
            passed += (mid / T[i]);
				//오버플로우 방지를 위해서 break 문 필요
            if(passed >= M)
                break;
        }
        
        if(passed < M){
            min = mid+1;
        }
        else{
            answer = mid;
            max = mid-1;
        }
    }
    
    cout << answer << endl;
    return 0;
}