[코딩테스트 C++] 입국심사
오늘의 문제
https://programmers.co.kr/learn/courses/30/lessons/43238
입국심사
나의 풀이(참고후 풀이)
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
long long solution(int n, vector<int> times) {
sort(times.begin(), times.end());
unsigned long long end = n * times[times.size()-1];
unsigned long long start = 1;
unsigned long long answer = 0;
while(start <= end){
unsigned long long mid = (start + end)/2;
unsigned long long people = 0;
for(int i=0;i<times.size();i++){
people += mid / times[i];
}
if(people >= n){
if(answer == 0)
answer = mid;
else
answer = min(answer, mid);
end = mid-1;
}else{
start = mid+1;
}
}
return answer;
}
모범 답안
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
long long solution(int n, vector<int> times) {
sort(times.begin(), times.end());
long long left = (long long)times[0];
long long right = (long long)times[times.size() - 1] * n;
long long answer = right;
while(left <= right){
long long mid = (right + left) / 2;
long long pass = 0;
for(int i = 0; i < times.size(); ++i)
pass += mid / (long long)times[i];
if(pass >= n){
right = mid - 1;
if(mid <= answer)
answer = mid;
}
else
left = mid + 1;
}
return answer;
}
배울점
- 문제 유형이 이분탐색이길래 아.. 뭘 이분탐색하는거야 했는데 이런거였다. 와..
- 최대 시간을 잡은 후 거기서부터 이분탐색을 시작한다.. 그 지점에서의 사람 수를 구하고 더 해야겠으면 위로 아님 아래로 내려간다. 이게 이분탐색이구나
- mid를 구하고 최소값을 구하는 방법을 따로 넣는것이아니라 answer가 저장되면 그때부터는 최소를 찾는것
- start <= end이 될때까지 수행
- 이진탐색을 구현한지 오래되었다고 또 까먹었다. 내일 다시 풀어서 개념을 확인하자
- 또 unsigned long long을 쓰는 문제는 처음봤다.
- long long 의 범위는 -9,000,000,000,000,000,000 ~ 9,000,000,000,000,000,000 정도라고 한다
- unsigned long long은 0 ~ 18,000,000,000,000,000,000 쯤이겠다
Author And Source
이 문제에 관하여([코딩테스트 C++] 입국심사), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@huijae0817/코딩테스트-C-입국심사저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)