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

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

프로그래머스

문제를 먼저 읽고 그리디로 푸는 것인가 했는데 다음과 같은 제한사항이 있었다.

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

그래서 그리디는 아니고 이분탐색인가 했는데

적혀 있어서 알아버렸다.

 

이분탐색인것을 알아도 어떻게 풀지 몰라서 해맸다.

문제에서 최소 시간을 답으로 출력하라고 하니까 뭔가 시간을 기준으로 푸는 것 같았다.

그렇게 하려면 어떻게 해야하는지 그려봤다.

풀이

1.times를 오름차순으로 정렬한다.

2. 시간을 정한다. 

3.시간 안에 각 심사관이 몇명을 검사할 수 있는지  times의 앞부분부터 체크한다. 

4-1.  검사할 수 있는 인원이 n 보다 크게 되면 시간이 더 적어저도 검사할 수 있으므로 시간을 줄인다. (r = mid -1)
4-2 . 모든 심사관이 시간 안에 최대로 검사를 했는데도 (for 문이 끝났는데도) 검사할 수 있는 인원이 n 보다 작게되면 
         시간을 늘려서 검사를 더 해야한다.
5. l을 출력해주면 된다.

헷갈리는 부분

이분탐색을 할때 r이나 l을 바꾸어주는 조건을 정할때 (>,<=) 등호를 어느쪽에 붙여줘야하는지 헷갈린다.

또 출력을 mid, r, l 중에 무엇을 해야하는지 헷갈린다. 그래서 찾아본 글들!

https://www.acmicpc.net/blog/view/109

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

https://blog.naver.com/jinhan814/222156334908

이분 탐색, 파라메트릭 서치 안 헷갈리는 TIP

코드

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

long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(),times.end());
    long long l=0,r=1000000000000000001,mid=0;
    long long tmp=0;
    long long nn=n;
   int size=times.size();
    while(l<=r)
    {
        nn=n;
        //cout<<mid<<endl;
        mid=(l+r)/2;
        for(int i=0;i<size;i++)
        {
             tmp=mid/times[i];
            nn-=tmp;
            if(nn<=0)
            {
                r=mid-1;
                break;
            }
           
         }
         if(nn>0)
             l=mid+1;
        
    }
    answer=l;
    return answer;
}