3020번: 개똥벌레
개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이
www.acmicpc.net
많은 사람들이 lower_bound와 upper_bound함수를 사용해 이분탐색 알고리즘을 사용해 푼 것을 문제를 맞추고 나서 알 수 있었다.
난 처음엔 그냥 완탐으로 풀려다 시간 초과가 발생하는 바람에 누적합 알고리즘과 비슷하게 문제를 풀 수 있었다.
1. 석순과 종유석 벡터를 각각 생성 후 장애물이 마지막으로 지나는 부분의 벡터 값을 증가시켜주었다.(상한선 하한선 생성)
2. 그 후 크기가 1인 석순은 크기가 2인 석순을 지날 때 똑같이 부셔야 하므로 벡터의 모든 값을 갱신해주었다.
3. 마지막으로 두개의 벡터를 더한 값을 새로운 벡터에 넣어주고 그 벡터를 정렬 후 최소값과 그 갯수를 구할 수 있었다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, h, x;
cin >> n >> h;
vector<int> v1(h + 1);
vector<int> v2(h + 1);
vector<int> v3;
for (int i = 1; i <= n; i++) {
cin >> x;
if (i % 2 == 1) {
v1[x]++;
}
else {
v2[h+1-x]++;
}
}
for (int i = 1; i < h; i++) {
v2[i + 1] += v2[i];
v1[h - i] += v1[h + 1 - i];
}
for (int i = 1; i <= h; i++) {
v3.push_back(v1[i] + v2[i]);
}
sort(v3.begin(), v3.end());
int cnt = 1;
for (int i = 1; i < v3.size(); i++) {
if (v3[0] < v3[i]) {
break;
}
cnt++;
}
cout << v3[0] << " " << cnt;
return 0;
}lower_bound와 upper_bound 함수를 좀 더 공부해서 다음번엔 써먹어 봐야겠다!(하지만 속도랑 코드 크기는 별차이 안남;;)
