[Level 3] 입국심사 (C++)

진짜 이 문제에 시간 엄청 많이 쏟아 부었다. 

아무리봐도 이게 정답인데 계속 "6번 9번 테스트케이스"에서 오류가 났다. 

너무 스트레스 받아서 시간 보니까 3시간이 지나있었다. 

비쥬얼 스튜디오에서 모든 테스트 케이스 쳐보고 계산해보고 하던 것을 중단하고 남들이 짜놓은 코드를 확인하고 

검사해봐도 오류를 발견하지 못했다. 이진탐색은 다 똑같은 로직이기 때문에 이게 문제는 아니였던 거 같다. 

이진탐색을 한번이라도 풀어 본 사람은 제일 처음 변수를 start와 end를 가리키는 변수를 생성해야한다.

나는 해당 변수명을 l 과 h 로 보통 지정하는 편인데 각각 초기화를 1과  LLONG_MAX 로 지정하였다. 

근데 이렇게 하면 안된다. h에는 모든 사람이 제일 긴 심사 기간을 가지는 심사관한테 다 갔을 때 걸리는 시간을 지정해주어야한다. 

 

 

"h = times[times.size()-1] X 사람의 수" 로 설정
answer 값도 해당 값을 담자

즉, 이진탐색에서 answer값을 갱신 하지 않을 경우 미리 answer값을 h 로 초기화 시켜줘야한다.  

 

어떤 바보들이 다른 심사관을 놔두고 제일 긴 심사 시간을 가지는 심사관 앞에 다 줄을 서냐고.........

너 이진탐색 풀줄 아냐? 정도를 물어보고 로직을 제대로 짰는지에 대한 테스트케이스로만 구성했으면 좋겠다. 

지금 너무 화가 나서 좀 감정이 실렸다.. 자제하자. 시간을 너무 많이 써서 흥분했다. 

---

이진 탐색을 풀기 위해 좋은 문제들은 백준 문제에 "이진탐색" 카테고리에서 문제를 한번 풀어보고 오는것도 좋다. 

[백준 6236번 / C++] 용돈 관리

이진탐색 로직은 외워주는게 좋다 

위의 문제나 밑에 코드를 보면 항상 똑같은 로직이다. 

이 문제에서는 1초에서 ~ 어마어마한 시간을 시작 포인트, 끝 포인트로 정해서 그 중간값을 기준점(mid)을 두어 그 값으로 계속 비교해가면서 이진탐색을 시작한다. 

 

즉, mid값으로 벡터 안에 들어있는 각 원소는 심사시간을 가리키며 해당 원소를 나누었을 때 몫이 mid초 시간동안에 해당 심사관에서 통과시키는 사람의 수인 것이다. 

 

이러한 로직으로 사람을 카운팅 해주며 카운팅 된 사람의 수가 입력 받은 n 보다 더 많다면 시간을 좀 더 줄여보고 그렇지 않다면 시간을 좀 더 늘려보고 이런식으로 계속 진행하는 것이다.  

 

#include <string>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
typedef long long ll;
ll l , h; 
ll N;
bool check(ll mid, vector<int>& times) {
    ll p_cnt = 0;//사람 수
    for (int i = 0; i < times.size(); i++) {
        p_cnt += mid/times[i];
    }
    return p_cnt >=N;//시간안에 사람수가 더 많으면 시간 줄여
}
long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(),times.end());
    N = n;
    l=1;
    h = times[times.size()-1]; 
    h =h*n; 
    answer=h; 
    while (l <= h) {            
        ll mid = (l + h) / 2;  
        if (check(mid, times)) {
            h = mid-1;
            answer = mid;
        }
        else l = mid+1;
    }
    return answer;
}

 h = times[times.size()-1]*n; 이와 같이 하면 오류가 나서

 h = times[times.size()-1]하고 h = h*n 으로 해주었다. 

 

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