[BOJ/백준][Gold4] 3649 : 로봇 프로젝트 (C++)

www.acmicpc.net/problem/3649  

3649번: 로봇 프로젝트

 

[난이도] Gold4

[유형] 이분탐색

 

[풀이]

n이 10만이므로 O(n^2)으로 풀수가 없다.

정렬 후 조각을 한개 정한 뒤 이분탐색으로 나머지 조각을 찾아주면 된다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n,x,u=1e7,al,ar;
int main(){
    while(scanf("%d",&x) !=-1){
        bool ok = 0;
        al=ar=0;
        x*=u;
        scanf("%d",&n);
        vector<int> lego(n);
        for(int i=0;i<n;i++) scanf("%d",&lego[i]);
        sort(lego.begin(),lego.end());   
        for(int i=0;i<n;i++){
            int l = lego[i];
            auto it = lower_bound(lego.begin()+i+1,lego.end(),x-l);
            if(it != lego.end() && l+*it==x){
                if(!ok || ar-al < *it-l){
                    ok=1;
                    ar=*it;
                    al=l;
                }                
            }
        }
        if(ar==0) puts("danger");
        else printf("yes %d %d\n",al,ar);
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/3649.cpp