[백준] 3020-개똥벌레(C++)

문제링크:https://www.acmicpc.net/problem/3020

3020번: 개똥벌레

 

정렬문제입니다.

 

우선 일반적으로 생각할 수 있는 nXh 번 반복하여 값을 구하는 결과는 오답입니다. (시간초과)

 

O(n*h) = 200000 X 500000 번 반복하게 됩니다. 대략 1억번 반복에 1초라고 가정할때 당연한 결과 입니다.

 

완전탐색이 안된다면 고려해야할 것은 dp 혹은 그리디적 관점입니다. dp를 사용하기에는 결과값들 사이에 연관이 전혀 없습니다. 

 

정렬을 하고 결과값을 구할때 O(n)의 과정을 O(lgn)으로 줄일 수 있습니다. 

 

그방법은 이분탐색의 개념을 이용하는 것입니다. 정렬되어있는 상태라면 해당 높이를 기준으로 더큰 값들이 몇개 있는지 작은 값들이 몇개있는지 판단하는데 있어 평균적으로 lgn번의 탐색으로 값을 알 수 있습니다. 

 

직접구현해도 좋지만 C++의 lowerbound, upperbound를 사용해보겠습니다. 

 

사용 예시입니다. 선행조건은 꼭 정렬되어있는 배열을 넣어야합니다.

int val = lower_bound(arr, arr + n, num ) - arr ;
int val = upper_bound(arr, arr + n, num ) - arr ;

위처럼 사용하고 lower_bound는 arr배열의 0~n까지중  num값인덱스 중 제일 작은 값을 반환 합니다. 

upper_bound는 arr배열의 0~n까지중 num보다 큰 가장작은 값의 인덱스 값을 반환합니다.

즉 1 2 3 3 3 3 4 배열에서 num=2인 lowerbound는 1을 반환, upperbound는 2를 반환하는 형태입니다.

 

 

 

정답코드입니다. 

#include <iostream>
#include <algorithm>
using namespace std;
int arr[100001] = { 0 };
int arr2[100001] = { 0 };
int n, h;
int result = 200001, result_cnt = 0;


int main() {
	cin >> n >> h;

	for (int i = 0; i < n/2; i++) 
		cin >> arr[i ] >> arr2[i];
		
	sort(arr, arr + (n / 2));
	sort(arr2, arr2 + (n / 2));


	for (int i = 1; i <= h; i++) {

		int val = lower_bound(arr, arr + (n / 2), i ) - arr ;
		val += upper_bound(arr2, arr2 + (n / 2), h-i ) - arr2 ;
		val = n - val;

		if (result == val)
			result_cnt++;
		else if (result > val) { 
			result = val;
			result_cnt = 1;
		}
	}

	cout << result << ' ' << result_cnt << endl;

}