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

1. my

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

ll solution(int n, vector<int> times) {
    ll answer = 0;
    int l = times.size();
    vector<ll> t (l,0);
    vector<int> p (l,0);
    sort(times.begin(), times.end());

    while(n -- )
    {
        for(int i = 0 ; i < l ; i ++)
            t[i] += times[i];            
        
        int idx = min_element(t.begin(), t.end()) - t.begin();
        p[idx] ++;
        for(int i = 0 ; i < l ; i ++)
           if(i!=idx)  t[i] -= times[i];            
    }
    
    return t[max_element(t.begin(), t.end()) - t.begin()];
}

 

문제 분류의 이분탐색을 이미 보아서 틀릴줄 알았지만 그냥 풀어 봄

역시 시간초과 발생함.

이분탐색 문제 인 줄을 알고봐도 어떻게 써야 할 지 모르겠음

 

2. 이분탐색

다른 분들의 idea를 참고해서 작성함

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

ll solution(int n, vector<int> times) {
    ll answer = 0;
    ll l = 1;
    ll r = (ll) n* (*max_element(times.begin(), times.end()));
    ll h ; 
    while(l<=r)
    {
        h= (l+r)/2;
        ll n_temp = 0;
        for(int t : times)
            n_temp += h/t;
        
        if( n <= n_temp)
            {
                answer = h;
                r = h-1;
            }
        else
            l=h+1;
    }
   
   return answer;
}

int main()
{
    int n = 6;
    vector<int> times = {7,10};
    cout<<solution(n,times)<<endl;;
}

시간을 기준으로 이분 탐색을 때릴 생각을 못하고 계속 검역대 라인 기준으로 생각을 해서 위 방식을 생각하지 못했다.