[C++] 백준 3020 : 개똥벌레

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

3020번: 개똥벌레

백준 3020번 개똥벌레를 풀었다.

 

석순과 종유석을 따로 입력받아서 정렬시킨다.

그 다음 이분탐색을 통해 높이에 따라 부딪히는 횟수를 구하고 min값과 비교한다.

최솟값이 갱신되면 카운트값을 1로 바꾼 후 반복문을 진행하고 최솟값과 똑같은 횟수라면 카운트값을 증가시킨다.

그러면 석순과 종유석을 부딪히는 횟수의 최솟값과 그런 구간의 개수를 구할 수 있다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int N, H;
vector<int> bot;
vector<int> top;

int main() {
	cin >> N >> H;
	for (int i = 0; i < N/2; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		bot.push_back(a);
		top.push_back(b);
	}

	sort(bot.begin(), bot.end());
	sort(top.begin(), top.end());

	int min = 1000000;
	int cnt = 0;
	for (int i = 1; i <= H; i++) {
		int botIndex, topIndex;
		botIndex = lower_bound(bot.begin(), bot.end(), i) - bot.begin();
		topIndex = lower_bound(top.begin(), top.end(), H - i + 1) - top.begin();
		int sum = N - (botIndex + topIndex);

		if (min > sum) {
			min = sum;
			cnt = 1;
		}
		else if (min == sum)
			cnt++;
	}

	cout << min << ' ' << cnt;

	return 0;
}