BOJ 3020 개똥벌레

BOJ 3020
이분탐색 문제로 처음 이 문제를 접하였다.
하지만 계속 고민을 해봐도 이분탐색으로는 생각이 나지 않았다.

스터디원에게 누적합이라는 힌트를 얻고
BOJ 21318
위 문제를 통해 누적합 감을 잡고
다시 개똥벌레를 풀어보았지만,,,,,
모든 높이를 점검해보는 방법(결국에 이방법으로 풀음)밖에
생각이 안나서 구글링을 해보았다...🤓

참고코드
upper_bound / lower_bound를 사용해서 해결했다!!

C++의 이분탐색

c++에서는 이진탐색으로 원소를 탐색하는 lower_bound / upper_bound를 사용한다.

배열 또는 리스트가 정렬되어있어야한다

이 조건이 성립되어야 사용가능하다.

이진탐색을 사용하기 위한 조건과 같다는 점을 알 수 있다.

또한 이진탐색의 원리를 갖고있기 때문에 O(logN) 시간복잡도를 갖습니다.

lower_bound

• 이 함수는 찾고자 하는 key값과 크거나 같은 원소의 위치를 구하는 것 입니다.
• 같은 원소가 여러개 있어도 유일한 해를 찾을 수 있습니다.
• 사용방법

template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

lower_bound(v.first(), v.end(), 4);
이런식으로 사용합니다.

upper_bound

• key값을 초과하는 가장 첫 번째 원소의 위치를 구하는 것 입니다.
• 같은 원소가 여러개 있어도 유일한 해를 찾을 수 있습니다.
• 사용방법

template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

upper_bound(v.first(), v.end(), 4);
이런식으로 사용합니다.