[백준] 3020번 : 개똥벌레

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 이진 탐색 문제로, 석순과 종유석을 따로 저장하여 각각에 대해 lowerBound를 이용해 현재 층(구간)에서 부딪히는 석순 및 종유석 개수를 찾을 수 있다.

1) 장애물 개수, 동굴 깊이를 입력 받고 장애물 개수만큼 반복문을 돌려 석순 및 종유석 길이를 저장한다.

• 짝수 번째 순서에는 down에 push (석순)
• 홀수 번째 순서에는 up에 push (종유석)

2) down과 up을 오름차순 정렬하여 이진 탐색이 가능하도록 해준다.

3) down과 up에 대해 lowerBound를 실행해 각 층에서 부딪히는 장애물 개수를 확인한다.

• lowerBoundDown(int currentFloor, int length)
  • start = 0, end = (down의 길이 - 1)로 초기화 해준다.
  • end가 start보다 크지 않을 때까지 아래 내용을 반복하며 down에서 (현재 층 + 1) 이상이 처음 나오는 인덱스를 찾는다.
    • mid = (start와 end의 중간 값)으로 초기화해준다.
    • 만약 (현재 층수 + 1) <= down[mid]라면 end = mid로 초기화
    • 만약 (현재 층수 + 1) > down[mid]라면 start = mid + 1로 초기화
  • 위 반복이 끝났을 때
    • (현재 층수 + 1) 이상의 값을 찾을 수 없었다면 0을 리턴한다.
      • lowerBound에서 타겟값을 못 찾으면 end는 가장 마지막 인덱스를 가리키게 됨.
    • 찾았다면 down의 크기 - end 값이 현재 층에서 부딪히는 석순 개수이다.
• lowerBoundUp(int currentFloor, int length, int height)
  • start = 0, end = (up의 길이 - 1)로 초기화 해준다.
  • end가 start보다 크지 않을 때까지 아래 내용을 반복하며 up에서 (동굴 높이 - 현재 층수) 이상이 처음 나오는 인덱스를 찾는다.
    • mid = (start와 end의 중간 값)으로 초기화해준다.
    • 만약 (동굴 높이 - 현재 층수) <= up[mid]라면 end = mid로 초기화
    • 만약 (동굴 높이 - 현재 층수) > up[mid]라면 start = mid + 1로 초기화
  • 위 반복이 끝났을 때
    • (동굴 높이 - 현재 층수) 이상의 값을 찾을 수 없었다면 0을 리턴한다.
      • lowerBound에서 타겟값을 못 찾으면 end는 가장 마지막 인덱스를 가리키게 됨.
    • 찾았다면 down의 크기 - end 값이 현재 층에서 부딪히는 석순 개수이다.

4) 각 층에 대해 lowerBoundDown과 lowerBoundUp을 실행해 두 함수의 결과 값을 더하여 각 층에서 부딪히는 총 장애물 개수를 구해 countEachFloor 벡터에 저장한다..

5) countEachFloor를 오름차순 정렬하면 부딪히는 장애물 갯수가 최솟값인 경우가 벡터의 앞쪽에 모이게 된다. 벡터를 탐색해 최소값이 아닐 때까지 minCount를 1씩 증가시키면 최종적으로 최솟값을 가지는 구간의 수가 저장된다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> down;				// 석순들 길이 저장
vector<int> up;					// 종유석들 길이 저장
vector<int> countEachFloor;		// 각 구간 장애물 개수 저장

// 현재 층에서 부딪히는 석순 개수 찾는 lowerBound ('현재 층 + 1' 이상이 처음 나오는 인덱스 찾아야 함)
int lowerBoundDown(int currentFloor, int length)
{
	int start = 0, end = down.size() - 1;

	while (end > start)
	{
		int mid = (start + end) / 2;
		
		if (currentFloor + 1 <= down[mid])
			end = mid;
		else
			start = mid + 1;
	}
	if (down[end] < currentFloor + 1)
		return 0;

	return ((int)down.size()) - end;
}

// 현재 층에서 부딪히는 종유석 개수 찾는 lowerBound ('동굴 높이 - 현재 층' 이상이 처음 나오는 인덱스 찾아야 함)
int lowerBoundUp(int currentFloor, int length, int height)
{
	int start = 0, end = up.size() - 1;

	while (end > start)
	{
		int mid = (start + end) / 2;

		if (height - currentFloor <= up[mid])
			end = mid;
		else
			start = mid + 1;
	}
	if (up[end] < height - currentFloor)
		return 0;

	return ((int)up.size()) - end;
}

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

	int n, h;
	cin >> n >> h;

	for (int i = 0; i < n; i++)
	{
		int value;
		cin >> value;
		if (i % 2 == 0)
			down.push_back(value);
		else
			up.push_back(value);
	}

	sort(down.begin(), down.end());
	sort(up.begin(), up.end());

	for (int i = 0; i < h; i++)
	{
		int downCount = lowerBoundDown(i, n);
		int upCount = lowerBoundUp(i, n, h);
		countEachFloor.push_back(downCount + upCount);
	}

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

	int min = countEachFloor[0];
	int minCount = 0;
	for (int i = 0; i < countEachFloor.size(); i++)
	{
		if (countEachFloor[i] == min)
			minCount++;
		else
			break;
	}
	cout << min << ' ' << minCount;
}