[백준 3649번] 로봇 프로젝트(C++ / 투포인터, 이분탐색)

일단 자꾸 틀리게 되는 원인이였던,

각 테스트 케이스마다 블록 list인 L을 초기화 안해주고 사용했던거랑,

테스트 케이스 수를 주지 않고 while(cin.eof() != EOF)로 했는데 제대로 작동하지 않았던 점.

위 2개의 원인이 시간을 엄청나게 잡아먹었다. 찾느라 애먹음 ㅠ;

 

아이디어

1. 투포인터

투포인터는 블록 list L을 일단 정렬 후, 양 끝점에서부터 시작해서 두개의 합이 구멍의 크기와 같으면 결과값을 찾은 것이니 즉각 리턴, 구멍의 크기(target)보다 작다면 head index를 1증가해서 다시 한번 테스트. 크다면 반대로 tail값 -1.

 

2. 이분탐색

투포인터로 풀었는데, 이분탐색으로도 풀길레 나도 풀어봤다.

마찬가지로 search로 들어가서 둘간의 head, tail간의 합 대신에 

for문에서 (target - 블록조각 길이)를 해주면 나머지 조각의 길이가 나오고, 그 조각의 길이를 이분탐색으로 찾아주면 된다.

 

C++ 투포인터 풀이

#include <bits/stdc++.h>
using namespace std;


pair<int,int> search(int target, vector<int>& l){
    // 정해진 구멍의 너비 = target
    // 레고조각들 길이 list l
    // 정렬시켜서 투포인터로 풀거임.
    target = target * 10000000;
    int head, tail;
    pair<int,int> res = {-1,-1}; // 초기값. danger출력할 것.
    head = 0;
    tail = (int)l.size()-1;
    
    sort(l.begin(), l.end()); // 정렬

    while(head< tail){
        //합친게 타겟값과 같다면, 바로 리턴.
        if(l[head]+l[tail] == target) {
            res = {l[head], l[tail]};
            return res;
        }
        else if(l[head] + l[tail] < target)
            head++;
        else tail--;
    }
    return res;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int x,n;
    vector<int> l;
    //구멍 너비 x(cm), 레고조각의 수 n, 레고 조각의 길이 l(nm) 1m = 10^-9m = 10^-7cm
    while(1){
        l.clear();
        cin >> x >> n ;
        if(cin.eof())
            break;
        for(int j = 0 ; j< n; j++)
        {
            int tmp;
            cin >> tmp;
            l.push_back(tmp);
        }
        pair<int,int> res = search(x, l);
        if(res.first == -1 || res.second == -1) cout << "danger" << endl;
        else{
            cout << "yes "<< res.first << " " << res.second << endl;
        }
    }
    
}

C++ 이분탐색 풀이

#include <bits/stdc++.h>
using namespace std;


void search(int target, vector<int>& l){
    // 정해진 구멍의 너비 = target
    // 레고조각들 길이 list l
    // 정렬시켜서 이분탐색.
    target = target * 10000000;
    int left,right,mid;
    sort(l.begin(), l.end()); // 정렬
    for(int i = 0 ; i< (int)l.size()-1; i++)
    {
    	//찾아야 될 값 find.
        int find = target-l[i];
        
        //i+1부터 끝까지 탐색.
        left = i+1;
        right = (int)l.size();
        
        while(left <=right){
            mid = left + (right-left)/2;
            //찾을경우
            if(l[mid] == find){
                cout << "yes " << l[i] << " " << l[mid]<<endl;
                return;
            }
            if(l[mid] <find) left = mid+1;
            else right = mid-1;
        }
    }
    //못찾을경우 while문 빠져나와서 실행.
    cout << "danger" << endl;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int x,n;
    vector<int> l;
    //구멍 너비 x(cm), 레고조각의 수 n, 레고 조각의 길이 l(nm) 1m = 10^-9m = 10^-7cm
    while(1){
        cin >> x >> n ;
        if(cin.eof()) break;
        l.clear();
        for(int j = 0 ; j< n; j++)
        {
            int tmp;
            cin >> tmp;
            l.push_back(tmp);
        }
        search(x, l);

    }
    
}

투포인터(위), 이분탐색(아래)