[백준]3020_개똥벌레

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

Solved

✔ 알고리즘 분류: 이분탐색, 누적합
✔ [백준]2805_나무자르기 문제가 생각난다.
✔ 이분탐색❤누적합
✔ 데이터세팅: sum[i]는 길이 n에 걸쳐 i번째 높이에 있는 장애물들의 총합을 의미한다.
시작 할때 모든 sum[i]에 장애물들의 총합을 넣기엔 중복도 많고 시간초과도 걸리니 각 석순/종유석의 꼭지점에만 sum[i]=1 또는 종유석 종료의 의미의 -1을 넣자.
✔ 그렇게 높이 1부터 h까지 순회하며 sum[i] += sum[i-1]로 i번째 높이에 있는 장애물들의 총합을 구할 수 있고 가장 작은 총합과 그 개수를 구하면 정답이다. (누적합)

using namespace std;
#include <iostream>
#define MAX 500001

int sum[MAX];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, h;
	int x;
	cin >> n >> h;
	for (int i = 0; i < n; i++) {
		cin >> x;
		if (i % 2 == 0) { //석순
			sum[h - x + 1]++;
		}
		else { //종유석
			sum[1]++;
			sum[x + 1]--;
		}
	}
	int answer = -1;
	int cnt=0;
	for (int i = 1; i <= h; i++) {
		sum[i] += sum[i - 1];
		if(answer==-1 || sum[i]<answer){
			answer = sum[i];
			cnt = 1;
		}
		else if (sum[i] == answer) {
			cnt++;
		}
	}
	cout << answer << ' ' << cnt << '\n';
	return 0;
}