(C++) - 백준(BOJ) 2428번 : 표절 답

www.acmicpc.net/problem/2428

2428번: 표절

이분탐색 문제였습니다.

 

풀이방법

 * 모든 파일이 크기가 1억으로 동일할 경우 파일의 개수가 10만개라면 pair의 개수가 int범위를 초과할 수 있으니 long long형으로 답과 함수 자료형을 선언했습니다. 

 

 1. 입력 file값을 오름차순으로 정렬합니다.

 

 2. 현재 index를 가장 큰 값으로 가정, 0 ~ index - 1까지 파일사이즈가 90%보다 작은 구간(검사 필요 없는 구간)을 찾습니다. 

 

 3. index - l가 쌍의 개수가 됩니다.

 

 4. 두 번째 file부터 모든 file에 대해 1 ~3을 수행합니다.

 

 

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
double file[100001];
ll ans;

ll binarySearch(double fileSize,int idx){
    int l = 0;
    int r = idx-1;
    int cnt = 0;

    while(l <= r){
        int mid = (l + r) / 2; 
        if(file[mid] < fileSize * 0.9 ) l = mid + 1; 
        else r = mid - 1;
    }
    return idx - l;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> file[i];
    sort(file,file+n);
    for(int i = 1; i < n; i++) ans += binarySearch(file[i],i);
    cout << ans <<'\n';
}