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

백준 3020번 개똥벌레

✍ 문제

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

(중략)

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

(중략)

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

✍ 입력

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

✍ 출력

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.

✅ 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

long long tree[2100000];
int idx; //첫 번째 leaf node의 index값

//구간 i-j에 +1
void edit(int i, int j) {
	int l = idx + i - 1;
	int r = idx + j - 1;

	while (l <= r) {
		if (l % 2 == 1) tree[l++] += 1;
		if (r % 2 == 0) tree[r--] += 1;

		l /= 2;
		r /= 2;
	}
}

//i 위치의 장애물 개수
int get(int i) {
	int result = 0;
	int nidx = idx + i - 1;

	while (nidx > 0) {
		result += tree[nidx];
		nidx /= 2;
	}

	return result;
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, h, o; //n: 길이, h:높이, o:장애물
	cin >> n >> h;

	for (idx = 1; idx < h; idx *= 2);

	for (int i = 1; i <= n; i++) {
		cin >> o;
		if (i % 2 == 1) edit(1, o);
		else edit(h - o + 1, h);
	}

	//장애물의 최솟값, 그 구간의 수
	int min = 200001;
	int min_num = 1;

	for (int i = 1; i <= h; i++) {
		int io = get(i);
		if (io < min) {
			min_num = 1; //...^^*
			min = io;
		}
		else if (io == min) min_num++;
	}

	cout << min << " " << min_num;

	return 0;
}

✅ 코드풀이

구간갱신, 단일쿼리의 index tree를 이용한 구현이다.