[BOJ] 백준 3649 로봇 프로젝트

문제 링크

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

3649번: 로봇 프로젝트

 

두 블록 길이의 합이 정확히 구멍의 길이와 같은 블록을 찾는 문제입니다.

 

풀이

1) 구멍의 너비 x의 단위는 센티미터이므로, x에 10,000,000을 곱한다.

2) 레고 조각의 길이를 오름차순으로 정렬한다.

3) 앞에서부터 반복문을 돌리면서 lower_bound()로 적당한 값이 있는지 확인한다. 현재 보고 있는 길이를 p[i]라 하면 (*lower_bound(현재+1, 끝, x-p[i]) == x-p[i]) 인 경우가 답이다.

 

정답이 여러 개인 경우 $|l_1 - l_2|$가 가장 큰 것을 출력해야 합니다. 따라서 앞에서부터 보면서 정답을 찾자마자 출력하고 반복문을 탈출하면 됩니다.

 

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
ll x, p[1'001'000];
int n;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while(cin>>x){
        memset(p, 0, sizeof(p));
        x *= 10'000'000;
        cin>>n;
        for(int i=0; i<n; i++){
            cin>>p[i];
        }
        sort(p, p+n);
        for(int i=0; i<n-1 ;i++){
            ll c = *lower_bound(p+i+1, p+n, x-p[i]);
            if(c == x-p[i]){
                cout<<"yes " << p[i]<<' '<<c<<'\n';
                goto pass;
            }
        }    
        cout<<"danger\n";
pass:;
    }
}