[백준 2428] 표절

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

2428번: 표절

#include <cstdio>
#include <iostream>
#include <algorithm>
int N;
double files[100000 + 10];

long long int cnt;

void input(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%lf", &files[i]);
	}
}

int BS_lower(int start, int end, double target)	// 타겟보다 같거나 큰 값 중 가장 작은 값
{
	int s = start;
	int e = end;
	int pivot = 0;
	int lb = -1;	// 하한을 찾지 못한 경우 예외처리 하기 위해 


	while (s <= e) {
		pivot = (s + e) / 2;

		if (files[pivot] >= target) {
			lb = pivot;	// 하한값의 후보들을 lb에 담는다. 
			e = pivot - 1;	// 하한값의 후보들 중 가장 작은 값을 찾기 위함이다. 
		}
		else s = pivot + 1;
	}
	return lb;
}


int BS_upper(int start, int end, double target)	// 타겟보다 같거나 작은 값 중 가장 큰 값
{
	int s = start;
	int e = end;
	int pivot = 0;
	int ub = -1;


	while (s <= e) {
		pivot = (s + e) / 2;

		if (files[pivot] <= target) {
			ub = pivot;	// 상한값의 후보들을 ub에 담는다. 
			s = pivot + 1;	// 상한값의 후보들 중 가장 큰 값을 찾기 위함이다. 
		}
		else e = pivot - 1;
	}
	return ub;
}



void search_files(void)
{
	std::sort(files, files + N);	// 크기 기준 오름차순 정렬
	
	int lower = 0, upper = 0;
	for (int i = N - 1; i > 0; i--) {	// 가장 크기가 큰 것 부터 탐색
		double size = files[i] * 0.9;
		lower = BS_lower(0, i - 1, size);
		if (lower < 0) continue;
		else {
			upper = BS_upper(0, i - 1, files[i]);
		}
		cnt += (upper - lower + 1);
		//printf("%d %d %d %d \n", i, lower, upper, cnt);
	}
}

int main()
{
	input();
	search_files();
	printf("%lld", cnt);
	return 0;
}

이 문제는 '제출한 파일의 개수가 너무 많다' 와 '파일 크기 너무 다른 경우에는 그러한 쌍을 검사하지 않고 넘어간다'는 문제의 설명을 보고, 파일 크기를 기준으로 오름차순 정렬 후 이분탐색으로 풀어야겠다고 생각했다. 

 

 

// search_files( ) 함수

#include <algorithm>으로 sort 라이브러리를 사용하여 입력받은 파일을 오름차순으로 정렬했다. 

굳이 인덱스가 N - 1인 파일부터 탐색한 이유는, 문제에서의 부등식이 작은 파일의 범위를 나타내고 있기 때문이다. 즉, size(F_big) * 0.9 <= size(F_small) <= size(F_big) 과 같은 식을 도출할 수 있다. 따라서 해당 범위에 들어올 수 있는 작은 파일의 하한값과 상한값을 구하여 (upper - lower + 1) 을 해주면, 사이즈가 큰 파일(size(F_big))과 쌍을 이루어 검사할 수 있는 작은 파일들의 개수를 모두 구할 수 있다.

한편, size = files[i] * 0.9 변수의 타입을 double로 놓은 이유는 * 0.9 때문이다. 이 때문에 files배열도 double로 선언하였다. 참고로 int로 하면 틀린다. (해봐서 앎 ㅋ)

 

 

// BS_lower( ), BS_upper( ) 함수

size(F_small) 의 하한값을 구할 때는 타겟을 size(F_big) * 0.9로 삼아, 배열의 원소들 중 해당 값보다 큰 수 중 가장 작은 것을 선택하기 위해 이분탐색한다. 

size(F_small) 의 상한값을 구할 때는 타겟을 size(F_big)로 삼아, 배열의 원소들 중 해당 값보다 작은수 중 가장 큰 것을 선택하기 위해 이분탐색한다. 

 

마지막으로, 검사하는 파일의 개수가 int 범위를 넘어갈 수 있다. 인풋받은 파일 100,000개의 크기가 모두 같은 경우 최대 10,000,000,000개를 검사해야 하기 때문에 cnt 변수를 long long int로 선언하고 "%lld"로 출력해야 한다.