백준 온라인 저지
190214 BOJ 3020번 개똥벌레
Stolen Moments
2019. 2. 14. 13:23
정렬, 이분 탐색
- 정렬하고 나서 높이가 500000개 이므로 높이 하나 씩 탐색하는 방식으로 풀었다.
- 다른 사람들의 코드를 보니 입력 받자마자 배열에 갯수를 추가하는 방식으로 풀 수도 있더라.
N이 200000개 밖에 안되니 충분히 가능한 풀이고 내 풀이보다 더 빠르다.
풀이
1. 석순과 종유석을 각각 배열을 만들어 입력받는다
2. 두 배열을 정렬한다.
3. 아래 식에 따라 높이 1 부터 H 까지 수행한다.
높이 1 일 때 부숴야 할 갯수 = (석순 총 갯수 - 석순 높이가 0 이하 갯수) + (종유석 총 갯수 - 종유석 높이가 H - 1 이하 갯수)
높이 2 일 때 부숴야 할 갯수 = (석순 총 갯수 - 석순 높이가 1 이하 갯수) + (종유석 총 갯수 - 종유석 높이가 H - 2 이하 갯수)
...
높이 H 일 때 부숴야 할 갯수 = (석순 총 갯수 - 석순 높이가 H - 1 이하 갯수) + (종유석 총 갯수 - 종유석 높이가 0 이하 갯수)
여기서 배열은 정렬된 상태이므로 lower_bound를 이용해 높이가 x 이하인 갯수를 찾을 수 있다.
arr[8] = { 1,1,1,2,3,3,4,5 } 에서 lower_bound(arr, arr+8, 2) - arr 을 수행하면
2가 들어갈 수 있는 인덱스 3을 얻을 수 있는데 이것은 즉 2 이하의 요소 갯수가 3 이라는 것을 알 수 있다.
4. 수행하면서 최소값과 구간 수를 갱신한다.
소스 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include <iostream> #include <vector> #include <algorithm> #define FOR(i,a,b) for(int i = a; i < b; i++) #define endl '\n' #define ll long long #define mp(a,b) make_pair(a,b) #define sws ios::sync_with_stdio(false), cin.tie() #define MAX 1000000000 using namespace std; int N, H, tmp, ans = MAX, rng; vector<int> A, B; int main() { sws; cin >> N >> H; FOR(i, 0, N) { cin >> tmp; if (i % 2 == 0) A.push_back(tmp); else B.push_back(tmp); } sort(A.begin(), A.end()); sort(B.begin(), B.end()); int totA = A.size(), totB = B.size(); FOR(i, 1, H+1) { int x = totA - (lower_bound(A.begin(), A.end(), i) - A.begin()); int y = totB - (lower_bound(B.begin(), B.end(), H - i + 1) - B.begin()); if (ans > x + y) { ans = x + y; rng = 1; } else if (ans == x + y) rng++; } cout << ans << ' ' << rng; } | cs |
반응형