경주장
[프로그래머스] 입국심사 본문
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;;
}
시간을 기준으로 이분 탐색을 때릴 생각을 못하고 계속 검역대 라인 기준으로 생각을 해서 위 방식을 생각하지 못했다.
'코테 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 가장 먼 노드 (0) | 2021.03.16 |
---|---|
[프로그래머스] 순위 (0) | 2021.03.14 |