ALGORITHM/BOJ
[BOJ] 3020번 개똥벌레 (C++)
yegyeom
2022. 1. 5. 11:18
문제 (https://www.acmicpc.net/problem/3020)
3020번: 개똥벌레
개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이
www.acmicpc.net
문제를 읽고 고민을 하다가.. 예전에 푼 문제에서 lower_bound와 upper_bound를 사용했던 게 생각이 났다. 구현을 해봤지만 시간 초과가 발생했고 구글링으로 약간의 힌트를 얻은 후 구현했다.
석순과 종유석을 각각 입력받고 정렬한다. 정렬 후, 1부터 h까지 반복하며 각 높이일 때 몇 개의 장애물을 파괴하는지를 구한다. 이때 lower_bound를 사용하는 것이다. 장애물의 개수를 구하고 저장할 때 종유석의 경우 반대 방향이므로 변수를 주의해서 넣어주어야 한다.
해당 높이에서 파괴되는 장애물의 개수를 구했으면, 그 개수가 최솟값인지 확인해준다. 최솟값이 갱신되었다면 카운트를 1로 설정해주고, 최솟값과 일치하면 카운트를 증가시켜준다.
lower_bound: value 값 보다 크거나 같은 첫 번째 원소의 주소
upper_bound: 처음으로 value 값을 초과하는 원소의 주소
[소스코드]
[시간초과 소스코드]
