danbibibi
article thumbnail
Published 2024. 3. 20. 23:37
BOJ 3020번: 개똥벌레 문제 풀이/백준

1. 문제

문제 바로가기> BOJ 3020번: 개똥벌레

 

3020번: 개똥벌레

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이

www.acmicpc.net

 

2. 풀이

각각의 높이(h)로 날 때, 파괴하게 되는 장애물 수를 이분탐색을 이용해서 구해주었다.

석순, 종유석으로 나눠 하면서 이상한 부분에서 너무 헷갈렸다 ................

<cpp />
#include<iostream> #include<algorithm> #include<vector> using namespace std; int N, H; vector<int> up, down; // 석순, 종유석 void input(){ cin >> N >> H; for (int i = 0; i < N/2; i++){ int h1, h2; cin >> h1 >> h2; up.push_back(h1); // 석순 down.push_back(h2); // 종유석 } } int upper_bound(int val, vector<int> &v){ int low=0, mid, high=N/2, upper=N/2; while(low<=high){ mid = (low + high)/2; if(val < v[mid]) { upper = mid; high = mid-1; } else low = mid+1; } return upper; // val 초과 값이 처음 등장하는 위치 } void solve(){ // 1. 정렬 sort(up.begin(), up.end()); sort(down.begin(), down.end()); // 2. 이분 탐색 int val = MAXH, cnt = 0; for(int h=1; h<=H; h++){ int ss = upper_bound(h-1, up); // 파괴하지 않아도 되는 석순 int jys = upper_bound(H-h, down); // 파괴하지 않아도 되는 종유석 int destroy = N-(ss+jys); // 파괴해야하는 장애물 수 if(destroy < val){ // (1) 개똥벌레가 파괴해야하는 장애물의 최솟값 val = destroy; cnt = 1; } else if(destroy == val){ // (2) 그러한 구간이 총 몇 개 있는지 cnt++; } } // 3. 정답 출력 cout << val << " " << cnt; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("../test/input.txt", "r", stdin); input(); solve(); }

'문제 풀이 > 백준' 카테고리의 다른 글

BOJ 2617번: 구슬 찾기  (0) 2024.03.25
BOJ 20040번: 사이클 게임  (1) 2024.03.24
BOJ 16947번: 서울 지하철 2호선  (1) 2024.03.07
BOJ 5719번: 거의 최단 경로  (0) 2024.02.21
BOJ 12851번: 숨바꼭질 2  (0) 2024.02.21
profile

danbibibi

@danbibibi

꿈을 꾸는 시간은 멈춰 있는 것이 아냐 두려워하지 마 멈추지 마 푸른 꿈속으로