My Profile

김형훈

안녕하세요.
김형훈입니다.

백준 2470 두 용액

백준 2470 두 용액

2022년 11월 27일

2022년 11월 27일

cpp, 이분 탐색

문제

문제

풀이

풀이

lower_bound 함수를 이용해 자신의 음숫값과 제일 근접한 값의 인덱스를 탐색한다.

코드

코드

#include <bits/stdc++.h>

using namespace std;

int n;

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

    cin >> n;
    vector<int> arr(n);
    for(int i=0; i<n; ++i) cin >> arr[i];
    sort(arr.begin(),arr.end());
    int val_1 = 1'000'000'002, val_2 = 1'000'000'002;
    for(int i=0; i<n; ++i){
        // 각 수 별로 자신의 음수값의 lower_boud 인덱스값을 탐색
        int target = lower_bound(arr.begin(), arr.end(), -arr[i]) - arr.begin();
        // target-1, target, target+1 중 합이 0에 가까운 값으로 갱신
        if(target-1 >=0 && arr[target-1] != arr[i] && abs(arr[target-1] + arr[i]) < abs(val_1 + val_2)){
            val_1 = arr[target-1];
            val_2 = arr[i];
        }
        if(target != n && arr[target] != arr[i] && abs(arr[target] + arr[i]) < abs(val_1 + val_2)){
            val_1 = arr[target];
            val_2 = arr[i];
        }
        if(target+1 <= n-1 && arr[target+1] != arr[i] && abs(arr[target+1] + arr[i]) < abs(val_1 + val_2)){
            val_1 = arr[target+1];
            val_2 = arr[i];
        }
    }
    if(val_1 > val_2) swap(val_1,val_2);
    cout << val_1 << ' ' << val_2;
}

결과

결과

Copyright © 2024 Hyunghoon Kim