[기출 중] 프로그래머스 입국심사

[문제]

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

코딩테스트 연습 - 입국심사

 

[풀이]

이분탐색 카테고리에 들어있는 문제인지 모르고 동적계획법으로 풀어야겠다 해서 뻘짓을 엄청 했다...근데 이분탐색으로 풀으라고 진작에 알려줬어도 감도 못잡았을 것 같다.

이 문제를 이분탐색으로 풀기 위해서는 (총 심사 가능 인원) = (전체 심사시간) / (심사관 당 심사시간) 라는 것을 이해하면 된다.

먼저 가장 최악의 심사 시간은 times를 정렬했을 때 가장 심사시간이 긴 심사관이 전체 인원을 심사하는 시간이다. 예제로 주어진 6명, [7, 10] 에서는 10 * 6 = 60이 최대 심사 시간이 된다. 그렇다면 mid = 30이 되고, 30분 동안 심사 가능한 인원을 구할 수 있게된다. 한 사람 당 7분이 걸리는 심사관은 30분 동안 30 / 7 = 4명을 심사할 수 있고, 두 번째 심사관은 30 / 10 = 3명을 심사할 수 있다. 따라서 총 7명을 심사할 수 있는데, 이는 심사해야하는 6명보다 크므로 answer를 mid값으로 갱신 가능한 것이다.

 

long long max = times.back()*n; 으로하면 오른쪽 항이 모두 int여서 계산결과 역시 int값이 나와 실패하는 케이스가 존재한다. long long max = (long long)times.back()*n; 으로 자료형을 명시적으로 변화시켜주면 주어진 케이스를 모두 충족한다.

 

[코드]

#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.back()*n;
    long long sum;
    long long mid;
    while(min<=max){
        sum = 0;
        mid = (min + max) / 2;
        for(int i=0; i<times.size(); i++){
            sum += mid/times[i];
        }
        if(sum < n){
            min = mid +1;
        }
        else{
            max = mid-1;
            answer = mid;
        }
            
    }

    return answer;
}