백준 3020. 개똥벌레

https://www.acmicpc.net/problem/3020

3020번: 개똥벌레

 

아이디어를 떠올리는게 쉽지 않은 문제였다.

우선 석순과 종유석을 따로 계산해야 한다.

 

문제를 푸는데 핵심은 각 길이의 석순,종유석이 몇개인지 카운트해서 누적합을 계산하는 것이다. 

예를들어 문제에서 나온 예제의 석순의 길이는 {1,4,2,3,3,3,3} 이다. 

각 길이의 갯수를 카운팅하면 다음과 같다.

높이	1	2	3	4	5
갯수	1	1	4	1	0

 

큰 높이에서 작은 높이로 누적합을 구하면 다음과 같다.

높이	1	2	3	4	5
갯수	7	6	5	1	0

높이1 을 지나가면 7개의 벽을 뚫어야 하고,

높이2를 지나가면 6개의 벽을 뚫어야 한다.

.. 

 

 

 

종유석은 거꾸로 매달려있기 때문에 반대로 계산해야 한다. 

석순이 높이 2라면, 이는 아래(땅)에서 부터 위로 2칸 있다는 것이고, 즉 아래(땅)에서 부터 위로 두칸은 벽으로 막혀있다는 의미다.

종유석이 높이 2라면, 이는 위(천장)에서 부터 아래로 2칸 있다는 것이고, 즉 위(천장)에서 부터 아래로 두칸은 벽으로 막혀있다는 의미다.

종유석의 높이는 h로 주어지면 H - h + 1 로 계산하게 되면 아래(땅)에서 부터 몇칸 떨어진 지점까지가 종유석인지 알수 있다. 

 

예제에서 주어지는 종유석의 길이는 {3,2,4,4,3,2,3} 이고 위 식으로 계산하면 {3, 4, 2, 2, 3, 4, 3} 가 된다. 

첫번째 3은 아래(땅)에서 부터 위로 3칸 떨어진 지점까지 종유석이 내려와 있다는 것을 의미한다. 

높이	1	2	3	4	5
갯수	0	2	3	2	0

 

종유석은 반대로 작은 높이에서 큰 높이로 누적합을 구하면 다음과 같다. 

높이	1	2	3	4	5
갯수	0	2	5	7	7

높이 2를 지나면 2개의 종유석에 의해 가로막히고, 

높이 3을 지나면 5개의 종유석에 의해 가로 막힌다.

 

 

 

이제 석순과 종유석의 누적합을 더해준다.

높이	1	2	3	4	5
갯수	7	8	10	8	7

 

가장 작은 갯수는 7로서 개똥벌레가 파괴해야 하는 장애물의 최소 갯수이다.

7을 갖는 높이는 1과 5 두개이므로 그러한 구간은 총 두개 있다.

 

 

 

 

---

이분탐색으로 푸는 방법도 있었다.

 

1부터 H 높이까지를 탐색한다.

탐색하는 높이로 지나갔을때 몇개의 장애물 (석순 + 종유석)을 뚫어야 하는지 계산한다.

단순히 모든 석순,종유석을 탐색하면 높이 하나의 탐색에 O(N)이 걸리기 때문에 총 O(N*H)가 걸린다.

 

하지만 석순과 종유석을 각각 오름차순 정렬하고 이분탐색으로,

석순은 높이 h보다 크거나 같은 값(lower_bound)의 첫 출현 인덱스를 구하면 높이 h 보다 크거나 같은 석순의 갯수를 구할수 있다.

마찬가지로 종유석은 높이 h-i+1 보다 크거나 같은 값의 첫 출현 인덱스를 구하면 높이 h-i+1 보다 크거나 같은 종유석의 갯수를 구할수 있다.

두 값을 더하면 뚫어야 하는 장애물의 갯수를 알 수 있다. 

이렇게 하면 O(N*logN)에 끝낼수 있다.