[C++] 백준 2428:표절 (이분탐색)

문제링크

2428번: 표절

문제

세계적인 석유 재벌 "규현 조 압둘 티크리티 안드레스 후세인 리오넬 솔레르 살라 마리우 두스 산투스 펠리스 빈 자이드 술탄 친나왓 뱅거 7세"는 1등 상품으로 페라리를 걸고 프로그래밍 대회를 개최했다. 이 대회의 참석자는 총 N명이고 각각 솔루션 파일 1개를 제출했다. 이 솔루션 파일을 F1, F2, ..., Fn이라고 한다.

채점 결과를 발표하기 전에, 남의 것을 배낀 사람이 있는지 찾아내려고 한다. 이 대회의 주최측은 두 파일을 비교해서 너무 비슷한지 아닌지 판별하는 프로그램이 있다.

하지만, 제출한 파일의 개수가 너무 많아서, 모든 쌍을 검사한다면, 2012년 지구가 멸망할 때 까지도 검사를 해야할 판이다. 따라서, 파일 크기가 너무 다른 경우에는 그러한 쌍을 검사하지 않고 넘어가기로 했다.

좀더 정확하게 하기 위해서, 대회의 심판들은 두 파일이 있을 때, 작은 파일의 크기가 큰 파일 크기의 90%보다도 작을 때는, 이러한 쌍은 검사하지 않고 넘어가기로 했다. 따라서, (Fi, Fj) 쌍을 검사해야 하는데, 이때, i≠j이고, size(Fi) ≤ size(Fj)이면서, size(Fi) ≥ 0.9 × size(Fj)인 쌍만 검사하려고 한다.

몇 개의 쌍을 검사해야 하는 지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) 솔루션 파일의 크기는 정수이다.

출력

첫째 줄에 검사해야 하는 파일의 개수를 출력한다.

 

풀이

입력 받은 파일의 사이즈를 오름차순으로 정렬한다.

가장 마지막에 있는 원소부터 처음에 있는 원소까지 되돌아오면서 아래의 탐색을 반복한다.

이분 탐색을 통해 문제에서 제시한 범위를 만족하지 않는 값을 찾는다. 그러면 index - left의 수가 문제에서 제시한 범위를 만족한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;
 
vector<int> v;    // 사이즈
int n;
ll result;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    // 입력
    for (int i = 1; i <= n; i++) {
        int f;
        cin >> f;
        v.push_back(f);
    }
 
    // 오름차순 정렬
    sort(v.begin(), v.end());
 
    for (int i = 0; i < n; i++) {
        int left = 0;
        int right = i;
        int mid = 0;
 
        // 이분탐색
        while (left <= right) {
            mid = (left + right) / 2;
 
            if (v[mid] < v[i] * 0.9) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        result = result + i - left;
    }
 
    cout << result;
}

 

메모

37번 라인에서 v[mid]와 v[i]값을 비교해야 하는데 v[mid]와 v[right] 값을 비교해서 삽질을 많이했다..

 

[C++] 백준:1654번 랜선 자르기(이분 탐색)