[BOJ]1940번: 주몽

 

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

---

N 제한이 15,000 이므로 단순 O(N^2) 탐색을 하면 시간초과가 납니다.

 

N개의 숫자를 오름차순 정렬을 한 뒤

 

앞에서 부터 하나씩 숫자를 탐색하면서

 

특정 숫자가 조합할 수 있는 대상이 되는 숫자를 선형 탐색이 아닌 이분 탐색을 하면 됩니다.

 

그러면 시간복잡도는 O(NlogN)으로 통과할 수 있습니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1940.cc