[BOJ 3020] 개똥벌레 C++

 

3020번: 개똥벌레

 

 

문제풀이

 

동굴의 길이가 N미터이고, 높이는 H미터이다.

이 동굴은 석순과 종유석으로 가득차 있는데 첫 번째 장애물은 항상 석순이고 그 다음부터는 종유석과 석순이 번갈아가면서 등장한다.

 

개똥벌레는 자신이 지나갈 구간을 정하면 일직선으로 지나가면서 모든 장애물을 파괴한다.

개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 문제다.

 

먼저 석순과 종유석을 따로 배열에 저장한다.

obs1은 석순이고 obs2는 종유석이다.

 

구간은 아래에서부터 시작해서 1부터 h까지 있고 구간별로 파괴하는 석순과 종유석의 개수를 lower_bound를 써서 구해주면 된다.

석순은 바닥에 있으므로 obs1[i] ≥ 구간인 석순들이 파괴된다.

종유석은 천장에 있으므로 obs2[i] ≥ h - 구간 + 1인 종유석들이 파괴된다.

 

 

1을 더해주는 이유는 위 그림을 보면 알 수 있다.

2번째 구간은 길이가 1인 석순과 길이가 2인 석순의 중간지점을 말한다.

첫번째 종유석의 길이가 3이므로 h - 구간 = 2이다.

첫번째 종유석을 파괴하지 않지만 파괴해야하는 장애물에 포함시키게 되는 것이다.

따라서 1을 더해줘서 h - 구간 + 1인 종유석들만 파괴하도록 해주어야 한다.

 

 

C++ 코드