Beakjoon 3649 로봇 프로젝트

03 Feb 2021 in Algorithm

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

나의 풀이

이 문제는 이진 탐색으로 해결할 수 있는 문제이다.

이 문제에서 첫 번째 레고 조각의 길이가 L2일 때 구멍을 완벽하게 막을 수 있는 다른 조각 L1 = x-L2 이기 때문에 하나의 조각을 알면 구해야 할 다른 조각의 길이를 알게 된다.

이를 통해 길이가 긴 레고 조각부터 반대편 레고 조각을 이진 탐색을 통해 찾을 수 있다. 문제에서 정답이 여러 개인 경우 (L1-L2)의 절댓값이 가장 큰 것을 출력해야 하지만 레고 조각이 클 수록 반대편 레고 조각 길이와 차이가 많이 나기 때문에 먼저 반대편 조각을 찾은 경우가 정답이 된다.

그 외에 이 문제에서 유의할 점은 “입력은 여러 개의 테스트 케이스로 이루어져 있다.”라는 입력 조건이 있기 때문에 cin을 사용할 경우 “if(cin.eof() == true) break; “ 를 통해 마지막 테스트 케이스가 끝나면 종료하도록 해야 하고, scanf를 사용할 경우 “while(scanf(“%d”,&x)==1)”와 같은 방식으로 처리할 수 있다. 또한 반복적으로 실행되기 때문에 초기화가 필요한 변수는 반드시 초기화를 해주어야 하며, 마지막 출력에 줄 바꿈도 추가해 주어야 한다.

풀이 코드 : 3649 로봇 프로젝트

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(int a, int b) {return a>b;}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    while(1){
        int x, n, num;
        cin>>x>>n;
        if(cin.eof() == true) break; 
        x *= 10000000;
        vector<int> arr;
        for(int i=0;i<n;i++){
            cin>>num;
            arr.push_back(num);
        }

        sort(arr.begin(), arr.end(), compare);

        int l1, l2;
        bool answer = false;

        for(int i=0;!answer && i<n;i++){
            if(arr[i] < x/2) break;
            int start = i + 1;
            int end = n - 1;
            int mid;
            int key = x - arr[i];
            while(start <= end){
                mid = (start + end)/2;
                if(mid != i && key == arr[mid]){
                    answer = true;
                    l1 = key;
                    l2 = arr[i];
                    break;
                }

                if(key > arr[mid]){
                    end = mid - 1;
                }
                else{
                    start = mid + 1;
                }
            }
        }

        if(answer){
            cout<<"yes "<<l1<<" "<<l2<<"\n";
        }
        else{
            cout<<"danger\n";
        }

        arr.clear();
    }
}

채점결과