[3649] 로봇 프로젝트

### Sort + Binary Search ###

[3649] 로봇 프로젝트 : http://boj.kr/3649

<소스코드>

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int x, n;
vector<int> lego;
 
void solve()
{
    for(int i=0; i<n-1; i++) {
        int cur = lego[i];
        if(binary_search(lego.begin()+i+1, lego.end(), x-cur)) {
            printf("yes %d %d\n", cur, x-cur);
            return ;
        }
    }
    puts("danger");
}
 
int main()
{
    while(scanf("%d", &x) == 1) {
        scanf("%d", &n);
        lego = vector<int>(n);
        for(int i=0; i<n; i++) {
            scanf("%d", &lego[i]);
        }
 
        x *= 10000000;
        sort(lego.begin(), lego.end());
        solve();
    }
}
 
 

>> 정렬 후 i 번째 값과 x-i번째 값이 [i+1, n-1] 구간에 존재하는지 확인. 

>> 시간복잡도 O(N*logN)