728x90
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/43238
KEY
- 시간을 기준으로 이분탐색한다는 방법 자체를 떠올리기가 어려운 문제다.
- 1분~가장 오래 걸리는 시간 까지 이분탐색으로 시간을 탐색하면서, 모든 사람이 심사를 받을 수 있는 시간 중 가장 짧은 시간대를 찾으면 된다.
- 시간을 심사대의 시간으로 나누어 더함으로써 완료할 수 있는 사람 수(cnt)를 센다. 가령 심사대는 7, 10분 두개가 있고, 지금 시간이 30분이라고 할 때, 완료할 수 있는 사람 수는 30/7 + 30/10 = 6이다.
- 자료형에 조심하자.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
long long solution(int n, vector<int> times) {
long long answer = 0;
//심사대 시간 오름차순
sort(times.begin(),times.end());
//가장 오래 걸리는 시간 = 가장 오래 걸리는 심사대에 모두 몰린 경우
long long end = (long long)times.back() * n;
long long start = 1;
while(start <= end){
long long mid = (start + end) / 2;
long long cnt = 0;
for(int i=0;i<times.size();i++){
cnt += mid / times[i];
}
if(cnt >= n){
end = mid - 1;
answer = mid;
}else{
start = mid + 1;
}
}
return answer;
}
|
cs |
728x90
'Algorithm > 이분탐색' 카테고리의 다른 글
[백준] 1920 수찾기 c++ (0) | 2023.03.31 |
---|---|
[백준] 1654 랜선 자르기 c++ (0) | 2023.02.25 |
댓글