백준 3020 : 개똥벌레

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

3020번: 개똥벌레

 

종유석 배열과 석순 배열을 따로 선언하고 값을 저장해준 뒤, 두 배열을 정렬하여 이분탐색을 활용하여 문제를 해결했다.

두 배열이 오름차순 정렬되어 있으므로  (각각의 배열의 크기 - 이분탐색으로 찾은 인덱스 위치 값) 을 계산해 현재 장애물의 개수를 체크했다.

 

시간복잡도는 h번 순회하면서 이분탐색을 수행하므로 O(h * logN) 이다.

 

#include <iostream>
#include <algorithm>

#define F_BOUND floor_arr, floor_arr + mid
#define C_BOUND ceil_arr, ceil_arr + mid
using namespace std;

int floor_arr[100'000];
int ceil_arr[100'000];

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, h, tmp, mid, cnt;
	int min_val = 1e9, min_val_cnt = 0;

	cin >> n >> h;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
        //i가 홀수일 시 천장 배열에 i/2위치에 넣기
        //i/2위치에 넣는 이유는 배열을 짝수배열 홀수배열 두개로 나눴기때문
		if (i & 1) ceil_arr[i>>1] = tmp;
        //i가 홀수일 시 바닥 배열에 i/2위치에 넣기
		else floor_arr[i>>1] = tmp;
	}
	
    //각각의 배열의 크기
	mid = n / 2;

	//이분탐색을 위한 정렬
	sort(F_BOUND);
	sort(C_BOUND);

	for (int i = 0; i < h; i++) {
		cnt = 0;
        //바닥 배열에서 높이가 i를 초과하는 원소의 수만큼 더해줌
		cnt += (mid - (upper_bound(F_BOUND, i) - floor_arr));
        //천장 배열에서 높이가 (h - i) 이상인 원소의 수만큼 더해줌
		cnt += (mid - (lower_bound(C_BOUND, h - i) - ceil_arr));

		//최소값 갱신 및 개수 체크
		if (min_val >= cnt) {
			if (min_val > cnt) {
				min_val = cnt;
				min_val_cnt = 0;
			}
			min_val_cnt++;
		}
	}
	
	cout << min_val << ' ' << min_val_cnt << '\n';
	return 0;
}

메모리: 2800 kb

시간: 60 ms

 

추가로 이 문제는 누적합으로도 풀 수 있다.

누적합 풀이는 아래 글을 참고했다.

https://blog.naver.com/jinhan814/222252619895

[BOJ] 3020번 - 개똥벌레

 

#include <iostream>
#include <algorithm>

#define BOUND arr, arr + h
using namespace std;

int arr[500'001];

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, h, tmp, mid, cnt;
	int min_val, min_val_cnt;

	cin >> n >> h;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		if (i & 1) arr[h - tmp]++, arr[h]--;
		else arr[0]++, arr[tmp]--;
	}

	for (int i = 1; i <= h; i++) {
		arr[i] += arr[i - 1];
	}

	min_val = *min_element(BOUND);
	min_val_cnt = count(BOUND, min_val);

	cout << min_val << ' ' << min_val_cnt << '\n';
	return 0;
}

메모리: 3972 kb

시간: 24 ms

 

누적합 풀이가 훨씬 간결하고 성능적으로도 우수하다.

이분탐색 풀이는 시간복잡도가 O(h * logN) 이었는데 반해 누적합풀이는 O(n) 의 시간복잡도를 갖는다.