✌️ 기발한 생각으로 풀어내서 내 자신이 뿌듯했는데 다른 사람들도 다 이렇게 풀었더라... 더 열심히 하자
이분탐색
이다.return
으로 받는 끝나는 시간을 돌리면 어떨까라는 생각을 함.return
으로 나올수 있는 최댓값을 right
에 삽입. for (int i = 0; i < times.size(); i++)
right = max((long long)times[i], right);
right *= n;
이분탐색
을 통해 심사관의 걸리는 시간을 모두 나눠서 더해줌.mid
를 answer에 넣어주고 right = mid -1
left = mid+1
#include <string>
#include <vector>
using namespace std;
long long solution(int n, vector<int> times) {
long long answer = 0;
long long left = 0;
long long right = 0;
long long mid = 0;
for(int i=0;i<times.size();i++)
right = max((long long)times[i], right);
right *= n;
while(left <= right)
{
mid = (left + right)/2;
long long sum = 0;
for(int i=0;i<times.size();i++)
sum+=(mid/times[i]);
if(sum >= n) {
right = mid-1;
answer = mid;
}
else left = mid+1;
}
return answer;
}
Level 3 문제. 더럽지 않은 문제였다.