취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3020번 문제인 개똥벌레이다.
문제는 아래 링크를 확인하자.

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

각각의 종유석과 석순의 시작점과 끝점을 이용하여, 각 높이지점에서 다음 높이지점으로 갈 때의 장애물의 수의 변화를 기록해두자. 이를 이용하면 h를 순서대로 둘러보면서 각 높이에서의 장애물의 개수를 바로바로 계산해낼 수 있다.

남은 일은 높이 h에서의 충돌 장애물의 개수를 직접 보고 문제의 답을 갱신해나가는 것이다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[500002];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, H; cin >> N >> H;
	for (int i = 0; i < N; i++) {
		if (i & 1) {
			int x; cin >> x;
			arr[H - x + 1]++;
			arr[H + 1]--;
		}
		else {
			int x; cin >> x;
			arr[1]++;
			arr[x + 1]--;
		}
	}
	int crash = 0, mn = 1000000007;
	int cnt = 0;
	for (int i = 1; i <= H; i++) {
		crash += arr[i];
		if (crash < mn) {
			mn = crash;
			cnt = 1;
		}
		else if (crash == mn) cnt++;
	}

	cout << mn << ' ' << cnt;
}