C++ / 백준 / 3020 / 개똥벌레

문제

 

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

3020번: 개똥벌레

 

 

문제풀이

 

계속 시도해 보다가 안 돼서 누적합이라는 분류를 보고 풀었다.

석순과 종유석을 구분해서 1부터 N까지 홀수 부분은 홀수 벡터에, 짝수 부분은 짝수 벡터에 따로 저장한다.

(인덱스는 길이)

 

위 그림(예제2)에서는 홀수 벡터는 {1, 1, 4, 1, 0}, 짝수 벡터는 {0, 2, 3, 2, 0}이 된다.

장애물의 높이가 2이면 높이가 1인 위치에서 닿으므로 누적합을 한다.

홀수 벡터는 높은 위치 부터 낮은 순으로 더한다. {7, 6, 5, 1, 0}

짝수 벡터도 높은(길이가 긴) 위치부터 낮은 순(길이가 짧은)으로 더한다. {7, 7, 5, 2, 0}

높이가 1인 위치에서는 석순의 높이는 1, 종유석의 높이가 5가 돼야 개똥벌레랑 닿으므로 홀수[1]+짝수[5], 홀수[2]+짝수[4], ... 이런 식으로 값을 저장하는 벡터를 만든다.

그러면 {7, 8, 10, 8, 7}이 된다.

이를 정렬 한뒤 upper_bound를 이용해 최솟값의 개수를 구한다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N(0), H(0);
	cin >> N >> H;

	vector<int>odd(H + 1, 0);
	vector<int>even(H + 1, 0);

	int height(0);
	for (int idx = 1; idx <= N; ++idx) {
		cin >> height;
		if (idx % 2 == 1) ++odd[height];
		else if (idx % 2 == 0) ++even[height];
	}
	for (height = H - 1; height >= 1; --height) {
		odd[height] += odd[height + 1];
		even[height] += even[height + 1];
	}

	vector<int>obstacle(H + 1, 0);
	for (height = 1; height <= H; ++height) {
		obstacle[height] = odd[height] + even[H - height + 1];
	}

	sort(obstacle.begin(), obstacle.end());
	int right = upper_bound(obstacle.begin() + 1, obstacle.end(), obstacle[1]) - obstacle.begin();
	cout << obstacle[1] << " " << right - 1;
}