이번 문제는 백준의 골드 5 문제 개똥벌레 문제이다.
문제를 차근차근 한 번 읽어보도록 하자.
최대 200,000의 동굴 길이가 주어진다.
동굴 길이에 대해서, 석순부터 시작하여 종유석과 석순이 차례로 주어진다.
둘은 반드시 번갈아가며 주어지며, 동굴의 길이 만큼 돌의 높이가 주어진다.
돌의 높이는 최대 500,000이며, 이제 개똥벌레가 동굴을 지나가려 한다.
동굴을 지날 때, 장애물을 파괴하면서 지나가려고 하는데
과연 어떤 높이로 날아야 최소한의 장애물을 파괴하고 지나갈 수 있을까?
문제 분석
먼저 우리가 제어할 수 있는 변인에 대해서 생각해보자.
우리는 지금 어떤 높이로 날아야 할 지를 정해야 하는 상황이다.
또한 각 높이에 대해 부딪히게 되는 장애물은 고정되어 있다.
따라서 우리는 높이를 바꾸어가며 최소 장애물 수를 찾아야 한다.
하지만 만약 이것을 그냥 단순 이중 for문으로 수행하게 된다면?
시간 복잡도가 O(H * N)이 되기 때문에 최악의 경우 O(200,000 * 500,000)이 된다.
이 값은 시간초과가 발생할 수 밖에 없는 값이라고 생각된다.
그럼 다른 방법을 통해 높이에 대해 부딪히는 장애물 수를 정해야 한다.
O(N^2) 보다 빠르게 탐색을 하려면, O(NlogN)으로 끝내는 방법이 있는데..
딱 떠오르는 방식이 바로 이분 탐색이다.
이분 탐색
높이를 1부터 H까지 탐색하며, 해당 높이보다 큰 장애물의 수를 센다면?
그럼 해당 장애물들은 반드시 부딪히게 되는 것이므로, 정답이 될 수가 있다.
이 논리를 아래와 같이 코드로 표현할 수 있다.
int count_stala(int target_stala[], int height) {
int left_v = 0, right_v = (cave_length / 2) - 1;
while (left_v <= right_v) {
int mid = (left_v + right_v) / 2;
if (target_stala[mid] < height)
left_v = mid + 1;
else
right_v = mid - 1;
}
return (cave_length / 2) - left_v;
}
for (int i = 1; i <= cave_height; i++) {
int collision_count = count_stala(stalactite, i) + count_stala(stalagmite, cave_height - i + 1);
}1부터 H까지 탐색하며, 주어진 높이보다 작아지는 첫 장애물의 index를 반환한다.
left가 움직일 조건이 target_stala[mid] < height와 같이 등호가 없는 조건이기 때문에,
같은 높이의 장애물들이 여러개일 경우, right의 값을 옮겨 뒤로 가게 된다.
결국 현재 높이보다 작은 가장 마지막 석순(종유석)에 대해서 동굴 길이 - index를 반환한다.
그럼 우리는 단 번에 해당 높이에서 몇 개의 석순(종유석)에 부딪힐 지 판단이 가능하다!
H의 모든 높이에 대해서 이분 탐색을 진행했으니, 결국 O(Hlog(N/2)) 의 시간복잡도를 갖는다.
단, 이분 탐색을 수행하기 이전에 장애물들은 반드시 높이를 기준으로 정렬 되어야 한다!
그래야 현재 높이 - 1의 장애물 뒤로는 모두 부딪힘을 반드시 보장할 수 있다.
최종적으로 아래와 같이 구현되었다.
누적 합
다른 사람들의 풀이를 참고해보니, 누적 합으로도 풀 수 있는 문제라고 한다.
이 방식이 훨씬 더 간단한 것 같다.
기존에는 길이를 칸으로 배열을 생성했다면, 높이를 칸으로 생성해보자.
즉, 아래와 같이 입력을 받는 것이다.
for (int i = 0; i < cave_length; i++) {
cin >> height;
if (i % 2 == 0)
stalagmite[height]++;
else
stalactite[cave_height - height + 1]++;
// 어느 높이에 장애물이 위치하는 지 기록한다.
}특정 높이에 대해서 몇 개의 장애물이 존재하는 지를 저장하는 것이다.
이후 두 배열에 대해서 누적 합을 아래와 같이 진행한다.
for (int i = 1; i <= cave_height; i++) {
stalactite[i] += stalactite[i - 1];
stalagmite[cave_height - i] += stalagmite[cave_height - i + 1];
}중요한 것은 석순의 경우에는, H - 현재 높이를 기준으로 누적 합을 진행해야 한다.
종유석은 아래에서부터 올라가면, 점점 만나는 장애물이 많아지는 것이 맞지만?
석순은 위에서부터 내려와야 점점 만나는 장애물이 많아지는 형태이기 때문이다!
이제 만든 누적합에 대해서 우리는 어떤 정보를 이용할 수 있을까?
바로 stalactite[i] + stalagmit[i]라는 정보를 얻을 수가 있다.
즉, 높이 i에 대해서 부딪힐 수 있는 석순과 종유석의 합이다!
최종적으로 해당 값에 대해서 아래와 같이 코드를 작성할 수 있다.
ll answer = 999999999;
int cnt = 0;
for (int i = 1; i <= cave_height; i++) {
ll curr_height = stalactite[i] + stalagmite[i];
if (curr_height < answer) {
cnt = 1;
answer = curr_height;
// 더 작게 부딪힐 수 있으면 갱신
}
else if (curr_height == answer)
cnt++;
}이분 탐색보다 훨씬 더 간단한 풀이라고 생각된다.
물론 이분 탐색의 경우 lower_bound와 upper_bound를 이용할 수 있을 것이다.
하지만 우선 기본에 충실하기 위해 직접 이분 탐색을 구현했다.
누적 합 방식은 풀이로써 떠올리기 굉장히 어려운 것 같다.
조금 더 노력해보자!