문제 : 개똥벌레
간단 요약
동굴에 석순이 있고, 종유석이 있고, 직선으로 비행할 때, 개똥벌레가 최소 충돌하는 수와 최소 충돌할 수 있는 구간의 수를 알아내자
데이터
N H 의미 장애물의 수(석순 + 종유석) 동굴의 높이 범위 2 ~ 200,000 2 ~ 500,000 접근법
문제점
우선 가장 편한건 0 ~ 동굴의 높이만큼 비행해보면서 그 때 얼마나 충돌하는지를 일일이 기록하고, 최소 충돌 횟수를 찾아서 그것과 같은 값이 나오는 것이 얼마인지를 알면 편하겠지만,
N이 20만, H가 50만으로 O(NxH)의 복잡도의 로직을 짤 경우 시간 초과가 발생하게 된다.그렇다면 어떻게 해야 할까
꼭 전체를 탐색하지 않더라도 높이 h로 비행했을 때 얼마나 부딪히는지를 알 수 있다면, 정확히는 O(N)만큼 장애물을 탐색하지 않더라도 얼마나 부딪힐 지를 알 수 있다면 시간 복잡도는 달라지고,
시간 초과 또한 달라질 수 있을 것이다.정답
이분탐색해결책
누적합을 이용한 풀이도 존재하지만 본 포스팅에서는 이분탐색으로 풀이를 진행한다.
앞서 O(N)만큼 탐색하지 않더라도 알 수 있다면 시간 복잡도가 달라질 것이라고 얘기하였다.
결론적으로 석순과 종유석 배열에 대해서 길이를 기준으로 정렬시킨다면 \(\begin{aligned} X \end{aligned}\) 높이로 비행할 때, 석순과 종유석 각각의 길이가 ~일 때 부딪히게 될 것이고,
정렬이 되어 있다면 이분 탐색을 통해 부딪히게 되는 가장 왼쪽의(가장 최소 조건의) 인덱스를 찾을 수 있고, 총 개수에서 인덱스만큼을 빼게 되면,
조건에 만족하는 장애물의 개수를 알 수 있을 것이다.그리고 이 경우 로직은 각 높이에 대해서 종유석과 석순의 인덱스를 찾는 것을 반복하므로 \(\begin{aligned} HlogN \end{aligned}\) 의 시간복잡도를 가지게 될 것이다.
코드를 보기 앞서 주의할 점은 방금 말한 X 높이로 비행할 때, 석순과 종유석의 길이에 대한 것인데,
백준의 경우 정수 길이의 중간 위치를 기준으로 비행하는 것으로 설명이 되어 있다(3과 4의 사이)그래서 숫자로 표현하자면 .5 같은 개념인데,
for문으로 돌릴 때 float은 좀 아닌 것 같았기 때문에, 내림한 값으로 생각해서 진행하였다.ex :
for(int i = 0; i < 3; i++)은 0.5,1.5,2,5 의 높이로 비행한다고 생각하면서 작성하였다.
코드
// file: "BOJ_3220.cpp" #include <iostream> #include <algorithm> #include <climits> using namespace std; // 석순을 저장할 배열 int suksoon[100001]; // 종유석을 저장할 배열 int jongusuk[100001]; // i.5 높이로 비행했을 때, 몇개의 장애물에 부딪히는지 저장할 배열 int crashReport[500001]; int n, h; // 석순을 대상으로 height과 같거나 큰 장애물 중 가장 왼쪽에 있는 인덱스를 구하기 위한 이분 탐색 int suksoonBinarySearch(int height){ int src = 0; int dst = n/2 - 1; while(src <= dst){ int mid = (src + dst) / 2; // 찾던 것과 같더라도 우측 슬라이드를 왼쪽으로 당기는 로직으로 src가 최대한 왼쪽 인덱스의 값을 찾도록 함 if(suksoon[mid] >= height){ dst = mid - 1; }else{ src = mid + 1; } } return src; } // 종유석을 대상으로 height과 같거나 큰 장애물 중 가장 왼쪽에 있는 인덱스를 구하기 위한 이분 탐색 // 딱히 석순 이분 탐색과 로직이 달라지는 건 없음, 인자를 배열로 줘서 불필요한 배열 복사를 피하기 위함 int jongusukBinarySearch(int height){ int src = 0; int dst = n/2 - 1; while(src <= dst){ int mid = (src + dst) / 2; // 찾던 것과 같더라도 우측 슬라이드를 왼쪽으로 당기는 로직으로 src가 최대한 왼쪽 인덱스의 값을 찾도록 함 if(jongusuk[mid] >= height){ dst = mid -1; }else{ src = mid + 1; } } return src; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> h; for(int i = 0; i < n; i++){ if(i % 2 == 0){ cin >> suksoon[i/2]; }else{ int height; cin >> height; jongusuk[(i-1)/2] = height; } } // 이분탐색 위한 종유석 정렬 sort(suksoon, suksoon + (n/2)); sort(jongusuk, jongusuk + (n/2)); // 0.5부터 (h-1)/5의 높이까지 반복하면서 해당 높이로 비행했을 때, 각각 종유석에 부딪히는 횟수랑 석순에 부딪히는 횟수를 계산할 것임 for(int i = 0; i < h; i++){ // 기본적으로 각각 종유석과 석순은 n/2개만큼 존재, 만약 i.5의 높이로 비행한다면 석순의 높이가 i+1일 때부터 석순에 부딪힐 것이므로 i+1높이 이상이면서 가장 작은 위치의 인덱스를 찾음 // 그럴 때, 석순 개수 - 인덱스는 총 부딪힐 장애물의 개수가 됨 // 종유석은 i.5의 높이로 비행을 할 때, h - i 높이 이상부터 부딪히게 되므로, h-i 높이 이상이면서 가장 작은 위치의 인덱스를 찾음 // 부딪힐 장애물의 개수는 석순 공식과 동일함 int crash = (n/2 - suksoonBinarySearch(i + 1)) + (n/2 - jongusukBinarySearch(h - i)); // 부딪힌 장애물 수를 기록 crashReport[i] = crash; } // 가장 적게 부딪힌 수를 알기 위해서 crashReport를 오름차순으로 정렬 sort(crashReport, crashReport + h); // 가장 앞에 있는 것이 적게 부딪힌 수가 되고 int minCrash = crashReport[0]; int answer = 0; // 작은 것부터 탐색해보면서 for(int i =0 ; i < h; i++){ // 만약 최소 충돌 횟수랑 같다면 최소 충돌 구간 횟수로 비행할 수 있는 구간이 있다는 뜻이므로 answer 증감 if(crashReport[i] == minCrash){ answer ++; } // 정렬을 했기 떄문에 만약 최소 충돌 횟수랑 다르다면 그 이상이고, 앞으로는 그것과 같거나 더 큰 충돌 횟수만 존재하므로 바로 탈출 else{ break; } } // 정답 출력 cout << minCrash << " " << answer; }
