백준 3020번 개똥벌레

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

사용한 알고리즘: 펜윅트리


높이가 5인 동굴을 생각해보면, 구간은 0.5 , 1.5 , 2.5 , 3.5 , 4.5 로 총 5개가 있습니다.
각 구간별로 갖는 장애물의 개수를 펜윅트리로 생각했습니다.
이에 따라 펜윅트리를 구현할 때, tree[1] = 0.5 구간, tree[2] = 1.5 구간 ... 등으로 생각했습니다. 천장을 0, 바닥을 H 의 높이로 생각해주었습니다.

각각의 입력에서 석순(바닥부터 자람)과 종유석(천장부터 자람)이 차지하는 구간들을 +1로 update 해주어 펜윅트리를 구성하였습니다. 예를들어 높이 5인 동굴에 석순이 3 크기이면,
이는 2초과 5미만인 구간, 즉 tree[3]: 2.5 , tree[4]: 3.5, tree[5]: 4.5 의 구간에 +1이 됩니다.
이후 1~H 의 구성된 구간중 최대값과, 개수를 찾아주었습니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 543211;
	int N, H, Lo, Hi, tree[MAX+1];
	int Li(int x){
	return x&(-x);
	}
	int sum(int i){
	int ans = 0;
	while(i>0){
	ans += tree[i];
	i -= Li(i);
	}
	return ans;
	}
	void update(int i, int diff){
	while(i<=H+1){
	tree[i] += diff;
	i += Li(i);
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> H;
	// tree[1]: 1번째 구간(=0.5), tree[2]: 2번째 구간(=1.5), ...
	for (int i = 0; i < N/2; ++i){
	cin >> Lo >> Hi;
	//석순
	update(H-Lo+1,1);
	update(H+1,-1);
	// 종유석
	update(1,1);
	update(Hi+1,-1);
	}
	int Whole = MAX;
	int cnt = 0;
	for (int i = 1; i <= H; ++i){
	int S = sum(i);
	if(S<Whole){
	Whole = S;
	cnt = 1;
	}
	else if(S==Whole) cnt++;
	}
	cout << Whole << ' ' << cnt << '\n';
	return 0;
	}

view raw BOJ 3020.cpp hosted with ❤ by GitHub