C++ / 백준 / 2428 / 표절

문제

 

https://www.acmicpc.net/problem/2428

2428번: 표절

 

 

 

문제풀이

 

두 파일이 있을 때 두 조건을 만족해야 한다.

1. 작은 파일 <= 큰 파일

2. 작은 파일 >= 큰 파일 * 0.9

따라서 이분 탐색인 lower_bound를 이용하여 문제를 푼다.

 

모든 입력을 받았으면 sort를 통해 오름차순으로 정렬한다.

 

0번째 파일부터 N-1번째 파일까지 탐색을 한다.

탐색하는 idx번째 파일을 큰 파일로 둔다.

그렇다면 정렬된 파일 중에서 두 조건을 만족하는 작은 파일의 시작 구간을 찾으면 된다.

lower_bound를 통해 기준 (idx번째) 파일의 0.9를 곱한 값 이상의 파일을 찾으면 된다.

 

 

코드

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0);
	cin >> N;
	
	vector<double>files(N, 0);
	int file(0);

	for (int idx = 0; idx < N; ++idx) {
		cin >> file;
		files[idx] = file;
	}

	sort(files.begin(), files.end());

	ll answer(0);

	for (int idx = 0; idx < N; ++idx) {
		file = files[idx];
		int start_idx = lower_bound(files.begin(), files.begin() + idx, file * 0.9) - files.begin();
		answer += idx - start_idx;
	}


	cout << answer;
}