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

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

프로그래머스

문제 분석

문제에서 요구하는 것은 각 심사관이 심사하는데 걸리는 시간과 사람의 수가 주어졌을 때, 모두가 심사를 받는데 걸리는 시간의 최솟값을 구하는 것이다.

문제 요구사항 자체는 복잡하지 않지만 문제는 제한사항이다.

입국심사를 기다리는 사람도 매우 많고, 각 심사관이 심사하는데 걸리는 시간도 커서 순회를 해서 구한다기보다는 나누기로 구할 생각을 해야한다. 

예를들어 입국 심사관이 각각 5, 7분에 한명씩 심사를 한다고 했을 때 100분동안 심사할 수 있는 사람은 100/5+100/7 = 34명이다.

아이디어

이 문제에서 주목할 점은 입국 심사를 하는 시간이 늘어날수록 더 많은 사람을 심사할 수 있다는 점이다. 즉 x축을 입국심사 시간, y축을 심사할 수 있는 사람의 수로 둔다면 증가하는 모양새를 보일 것이다. 

그래프의 모양을 저렇게 그리긴 했지만 중요한 것은 x가 증가하면 y도 증가하는 모양이라는 것이다. 즉 이분탐색을 통해 시간을 쪼개가며 주어진 n명의 인원을 심사할 수 있는 최적의 시간을 찾아낼 것이다. 

예를들어 아래와 같은 입출력이 주어졌을 때 최솟값과 최댓값의 중간값이 몇명을 심사할 수 있는지 판별한다. 여기서는 최소 1 최대 100으로 가정하겠다.

아래와 같이 최댓값과 최솟값을 적절히 조절하며 알맞은 답을 선택해가면 된다.

 

코드

이런 문제를 풀 때 가장 중요한 것은 mid를 구하는 식과 st와 en의 값을 적절히 설정하는 것이다. 이런 것들은 문제를 읽고 정해나가야 한다.

먼저 mid의 경우 조건을 만족하는 최댓값을 구하려면 mid=(st+en+1)/2를 해주어야 한다. 반대로 최솟값을 구하려면 mid = st+en으로 설정하면 된다.

그리고 st와 en을 설정하는 방법은 해당 값이 조건을 만족하는지를 잘 살피면 된다. 예를들면 위 예시에서 100분동안 6명을 검사할 수 있다. 다만 "최솟값"이 아닐 뿐이다. 그렇기에 en=mid로 초기화 해줬다.

반대로 25분동안은 6명을 검사할 수 없다. 6보다 작을 때는 st = mid+1로 초기화 해 주었다.

전체 코드는 아래와 같다.

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

long long solution(int n, vector<int> times) {
    long long answer = 0;
    long long a1=1000000000;
    
    long long st=1;
    long long en=a1*a1;
    long long mid=(st+en)/2;
    while(st!=en){
        mid=(st+en)/2;
        answer=0;
        for(auto k:times){
            answer+=mid/k;
        }
        if(answer>=n)en=mid;
        else st=mid+1;
    }
    return st;
}