[백준/c++] 3649번: 로봇 프로젝트

 

 

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

3649번: 로봇 프로젝트

 

 

아무리 생각해도 다 맞았는데 대체 왜 안 되는 건지 모르겠던 문제

딱히 반례라고 할 것도 없는 것 같은데 대체 왜 50%에서 멈추는지 화딱지가 났었는데

실수는 바로.. v를 초기화하지 않았던 것! 여러 테스트 케이스가 들어오기 때문에 두 조각의 정보가 들어가는 vector를 꼭 초기화했어야 했는데 안 했다...

 

이 문제는 두 포인터로 구현했다. 조각의 길이를 정렬하고 양 옆에서 둘을 더해서 

x보다 크면 R-- (L++를 하면 더 큰 값이 나오기 때문!)

x보다 작으면 L++ (R--를 하면 더 작은 값이 나오기 때문!)

x와 같다면 vector에 넣어주고, L++, R-- (vector에 넣어준 이유는.. 막을 수 있는 조각이 여러 개가 나올 수 있기 때문에 나중에 차이가 가장 많이 나는 걸 출력해야 해서 모아놔야 한다.)

 

 

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    long long x;
    int arr[1000001], nm = 10000000;
    vector<pair<int, int>> v;
    while(cin >> x){ //x = 구멍 너비, 단위 cm
        x *= nm;
        int n;
        cin >> n;    //블록 길이, 단위 nm (나노미터)
        for(int i=0; i<n; i++) cin >> arr[i];
        sort(arr, arr+n); //정렬
        
        int L = 0, R = n-1;
        while(L < R){
            long long value = arr[L] + arr[R];
            if(value > x) R--;
            else if(value < x) L++;
            else {
                v.push_back({arr[L], arr[R]});
                L++; R--;
            }
        }
        
        if(v.empty()) {
            cout << "danger\n";
            continue;
        }
        int maxv = abs(v[0].first - v[0].second);
        int ans1 = v[0].first, ans2 = v[0].second;
        if(v.size() > 1){
            for(int i=1; i<v.size(); i++){
                if(maxv < abs(v[i].first - v[i].second)){
                    maxv = abs(v[i].first - v[i].second);
                    ans1 = v[i].first;
                    ans2 = v[i].second;
                }
            }
        }
        cout << "yes ";
        if(ans1 >= ans2) cout << ans2 << ' ' << ans1 << '\n';
        else             cout << ans1 << ' ' << ans2 << '\n';
        v.clear();
    }
    return 0;
}