[백준 3020] 개똥벌레

문제

www.acmicpc.net/problem/3020

3020번: 개똥벌레

 

풀이

1. 구해야 하는 것은 벌레가 [1, h] 높이를 지나갈 때, ① 부서지는 석순의 개수의 최소 값과 ② 그러한 개수를 만족하는 높이의 개수를 구해야 합니다.

 

2. ②번부터 생각해본다면, 높이를 지날 때마다 부서지는 석순의 개수를 인덱스로 갖고 그러한 높이들의 개수를 값으로 갖는 맵(stl)을 사용하면 첫 번째 원소 값 기준으로 오름차순 정렬된 채로 유지되기에 결과적으로 답은 맵의 첫 번째 원소의 인덱스(부서진 석순의 최소 값)와 그 값(높이들의 개수)을 출력하면 해결할 수 있습니다.

 

3. 부서지는 석순의 개수는 벌레가 지나는 구간을 i라 할 때 ( i : [1, h]) 아래쪽에서 부서지는 석순들의 높이는 i이상이고, 위쪽에서 부서지는 석순들의 높이는 h - i + 1이상인 것들의 개수입니다. 또한 벌레가 지나갈 때 석순들이 서있는 순서와 관계없이 높이에 따라서 부서지므로 위, 아래 석순들을 오름차순으로 정렬한 후 lower_bound를 사용하여 위, 아래 석순의 전체개수에서 그 인덱스를 빼준다면 부서지는 석순의 개수를 구할 수 있습니다.

 

코드

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()

int n, h, ipt, usz, dsz, cnt1, cnt2;
vector<int> u, d;
map<int, int> mp;

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> h;
	for (int i = 0; i < n; i++) {
		cin >> ipt;
		if (i % 2) u.emplace_back(ipt);
		else d.emplace_back(ipt);
	}
	sort(all(u)), sort(all(d));
	usz= u.size(), dsz = d.size();
	for (int i = 1; i <= h; i++) {
		cnt1=  usz - (lower_bound(all(u), h - i + 1) - u.begin());
		cnt2 = dsz - (lower_bound(all(d), i) - d.begin());
		mp[cnt1 + cnt2]++;
	}
	cout << (*mp.begin()).first << " " << (*mp.begin()).second;
}