[백준 3020] 개똥벌레

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

3020번: 개똥벌레

요구사항

최소로 기둥을 부수는 높이 h와 이러한 높이의 개수 찾기

 

풀이

prefix sum이라는 개념을 활용하여

현재 높이의 기둥 부수는 수 = 현재 높이 기둥 + (현재 높이+1 기둥 들의 합)

을 이용하여 풀었다.

 

#include <iostream>

using namespace std;
int top[500002];
int bot[500002];
int topA[500002];
int botA[500002];
int main() {
	int n, h;
	cin >> n >> h;
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		if (i % 2 == 0)
			top[x]++;
		else
			bot[x]++;
	}
	for (int i = h; i >= 1; i--) {
		topA[i] = top[i] + topA[i + 1];
		botA[i] = bot[i] + botA[i + 1];
	}
	int ans = 987654321;
	int cnt = 0;
	for (int i = 1; i <=h ; i++) {
		int now = topA[i] + botA[h - i+1];
		if (ans > now) {
			ans = now;
			cnt = 1;
		}
		else if (ans == now) {
			cnt++;
		}
	}
	cout << ans << " " << cnt << endl;
}