Programmers_입국심사
7393 단어 programmersalgorithmcppalgorithm
✌️ 기발한 생각으로 풀어내서 내 자신이 뿌듯했는데 다른 사람들도 다 이렇게 풀었더라... 더 열심히 하자
- 필자의 경험상, 숫자의 범위가 10억을 넘어가면 거의 대부분
이분탐색
이다. - 10억이라는 수는 어마무시한 수기에 이분탐색을 안하게 되면 오버플로우
- 그렇다면 이분탐색으로 어떻게 돌릴까 생각을 하다가
return
으로 받는 끝나는 시간을 돌리면 어떨까라는 생각을 함. - 그래서 필자는
return
으로 나올수 있는 최댓값을right
에 삽입.
for (int i = 0; i < times.size(); i++)
right = max((long long)times[i], right);
right *= n;
- 이후,
이분탐색
을 통해 심사관의 걸리는 시간을 모두 나눠서 더해줌. - 이 값이 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 문제. 더럽지 않은 문제였다.
Author And Source
이 문제에 관하여(Programmers_입국심사), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@luck2901/Programmers입국심사저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)