(C++) - 백준(BOJ) 3649번 : 로봇 프로젝트

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

3649번: 로봇 프로젝트

이분탐색 문제였습니다.

 

 

풀이방법

 1. 입력 : 구멍의 단위가 cm으로 주어지기 때문에 nm으로 변경합니다. 1천만을 곱해주면됩니다. 이를 length라는 변수에 저장합니다. 이후 vector형 변수 lego에 n만큼 lego의 길이들을 입력받습니다. 

 

 2. lego를 오름차순으로 정렬합니다. 현재 확인하고 있는 한쪽 lego의 길이가 lego[i]일 때 length - lego[i]가 우리가 찾으려는 답입니다. lower_bound함수를 이용해 length -lego[i]를 key로해 정답을 찾습니다. 해당 값에 해당하는 index를 idx라는 int형 변수에 저장합니다.

 

* 자기 자신을 찾을 수도 있습니다. 자기 자신이 아니면서 lego[idx]가 정확히 length - lego[i]여야 합니다. 즉, 서로 다른 index를 2개 고를 수 있다면 정답입니다.

 

3. 정답을 출력합니다.

 

 

Code

#include <bits/stdc++.h>
#define NM 10000000
using namespace std;
int l;
int main(){
    while(cin >> l){
        int n;
        int length = l * NM;
        cin >> n;
        vector <int> lego(n);
        for(int i = 0, x; i < n; i++) cin >> lego[i];
        sort(lego.begin(),lego.end());
        int isFind = 0;
        for(int i = 0; i < n; i++){
            int key = length - lego[i];
            int idx = lower_bound(lego.begin(), lego.end(), key) - lego.begin();
            if(i != idx && lego[idx] == key) {
                isFind = 1;
                cout << "yes " << lego[i] << ' ' << lego[idx] << '\n';
                break;
            }
        }
        if(!isFind) cout << "danger\n";
    }
}