https://www.acmicpc.net/problem/2428
이진탐색을 이용하는 문제입니다.
문제부터 간단하게 요약하면,
파일의 유사도 검사를 해야하는데, 검사할 파일이 너무 많기에 각각의 두 파일을 모두 검사를 하게 되면, 너무 오래걸립니다. 그래서 두 파일이 있을 때, 두 파일의 크기가 [작은파일의 크기 >= 0.9*큰파일의 크기] 인 쌍들에 대해서만 검시를 하려 한다고 합니다.
이 때, 검사해야 하는 파일 쌍의 개수를 출력해야 합니다.
<Solution>
binary search를 이용해야 합니다.
binary search는 특정 값을 찾기 위해서도 쓰이지만, lower bound와 upper bound 를 찾는데에도 쓰입니다. 이 문제의 경우 파일을 크기 순으로 정렬 시켜 두고, 각각의 파일에 대해 본인 보다 크면서, [작은파일의 크기 >= 0.9*큰파일의 크기] 조건을 만족하는 가장 큰 upper bound를 찾아내면 쌍 수를 계산할 수 있습니다.
따라서 이 로직을 실제로 구현하면 됩니다.
코드는 아래와 같습니다.
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN ((int)1e5)
int N;//개수
double F[MAXN + 10];
void InputData(){
cin >> N;
for (int i=0; i<N; i++){
cin >> F[i];
}
}
int upper_bound_bs(int s, int e, double d){
int sol = -1;
while(e>=s){
int mid = (s+e)/2;
if(0.9*F[mid]<=d){
sol = mid;
s = mid+1;
}
else{
e = mid-1;
}
}
return sol;
}
long long solution(){
// sort
sort(F, F+N);
long long cnt = 0;
int upper_bound_index;
for(int i = 0; i<N-1; i++){
upper_bound_index = upper_bound_bs(i+1, N-1, F[i]);
// cout << "upper bound index : " << upper_bound_index<< endl;
if(upper_bound_index == -1) continue;
cnt+= (upper_bound_index-i);
}
return cnt;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long ans = -1;
InputData();// 입력받는 부분
// 여기서부터 작성
ans = solution();
cout << ans << "\n";// 출력하는 부분
return 0;
}
반응형
'코딩테스트 > C++ 문제풀이' 카테고리의 다른 글
[백준] 좋은 친구 (0) | 2022.11.25 |
---|---|
[백준] 용돈 관리 (0) | 2022.11.25 |
[백준] Social Distancing (1) | 2022.11.24 |
[백준] 폭탄제조 (0) | 2022.11.24 |
[정올] 저글링 방사능 오염 (0) | 2022.11.24 |