[BOJ]1590번: 캠프가는 영식

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

---

버스의 갯수 와 각 버스의 대수가 각 각 10만이므로 N^2 탐색을 하면 시간초과가 납니다.

 

그러므로 한 종류의 버스에 대해 영식이가 최소 몇 분을 더 기다려야하는지 계산할 때 logN만에 탐색해야 합니다.

그래야 NlogN으로 시간제한을 통과할 수 있습니다.

 

제가 logN으로 시간복잡도를 줄인 방법은 이분탐색입니다.

이분 탐색을 사용하여 버스 도착 시간의 상한과 하한을 계산해서 영식이가 탈 수 있는 최초 버스 시간을 구했습니다.  

---

코드: https://github.com/cotchan/algorithm/blob/main/java/BOJ/BOJ1590.java