[백준] 3649 로봇 프로젝트

레고 조각의 길이를 저장해서 정렬한 후 이분탐색으로 풀 수 있는 문제다

0부터 확인해서 구멍을 막을 길이가 정확하개 된다면

=> mid값을 찾는다면 출력하면 된다

처음에 set으로 모두 저장하고 풀려고했는데 시간초과가 났다

아무래도 값이 커서 저장하고 찾는데 시간이 오래걸리나보다

그래도 5초나줬는데..!!

 

집착하지말고 이분탐색으로 풀자!

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int t,n;
vector<int> vt;
 
bool bs(int pos,int val){
    int l = pos+1;
    int r = vt.size()-1;
    while(l<=r){
        int mid = (l+r)/2;
        if(vt[mid]==val) return true;
        if(vt[mid]>val) r = mid-1;
        else l = mid+1;
    }
    return false;
}
int main(){
    //freopen("input.txt","r",stdin);
    while(scanf("%d",&t) != -1){
        bool check = false;
        t*=10000000; vt.clear();
        scanf(" %d",&n);
        for(int i=0;i<n;i++){
            int a; scanf(" %d",&a);
            vt.push_back(a);
        }
        sort(vt.begin(),vt.end());
        for(int i=0;i<n;i++){
            int c = t-vt[i];
            if(bs(i,c)){
                printf("yes %d %d\n",vt[i],c); 
                check=true; break;
            }
        }
        if(!check) puts("danger");
    }
}