[백준 3649] 로봇 프로젝트 (C++)

문제 링크: www.acmicpc.net/problem/3649

3649번: 로봇 프로젝트

1. 주의할 점

- TC가 여러개 + 언제 끝나는지 알려주지 않음 -> EOF가 입력될 때까지 받는다

- 서로 다른 2 조각 사용

- TC마다 V 벡터 초기화

 

2. 구현

- if(cin>>len)을 통해 EOF를 입력 받았다면 false를, 아니라면 true를 입력 받기 때문에 EOF를 입력 받는다면 Break로 While문을 빠져 나간다

- 입력 받는 조각들을 오름차순으로 정렬한 이후, 양끝에서부터 안쪽으로 두 포인터를 이용하여 탐색한다(조각의 크기가 양수이므로 0의 경우 생각 안해도 된다)

- 만약 길이가 같다면 해당 조각들을 출력하고, 같지 않으면 l==r이 될때까지 조각 2개의 합(=Sum)이 구멍의 너비(=Len)보다 작다면 L++을 통해 조각의 합을 늘린다. 만약 반대로 작다면, R--를 통해 조각의 합을 줄인다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    vector<int> v;
    int len;
    while (1){
        if(cin>>len){
            len*=10000000;
            int num,val;
            cin>>num;
            v.clear();
            for(int i=0;i<num;i++){
                cin>> val;
                v.push_back(val);   
            }
            sort(v.begin(),v.end());
            int l=0,r=v.size()-1,sum;
            bool finish=false;
            while(l<r){
                sum = v[l]+v[r];
                if(sum==len){
                    finish = true;
                    cout << "yes "<< v[l]<<" "<<v[r]<<'\n';
                    break;
                }
                else if(sum < len)  l++;
                else r--;
            }
            if(!finish)
                cout << "danger\n";
        }
        else break;
    }
    return 0;
}