2467번 용액

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

 

이분탐색 문제다.

 

참고로 두 용액의 합이 0이 될 수도 있다.

 

1. 맨 처음 원소와 맨 마지막 원소의 비교를 처음으로 설정한다. L = 0, R = v.size() - 1

 

2. 비교할 값(pivot)을 설정해, 각각의 절댓값을 비교하여 pivot을 갱신한다.

절댓값을 활용하는 이유는 -와 +를 고려할 필요가 없이 무조건 둘 중 작은 값이 0에 가깝기 때문이다.

 

3. L과 R은 v의 인덱스이고, (v[L] + v[R])이 0을 기준으로 큰지, 작은지, 같은지 비교한다.

 

4. 3의 결과에 따라, L과 R을 적절히 연산한다.

 

처음에 틀렸었는데 Update 함수 내의 if 조건문에서 pivot > abs(sum)로 작성했었다.

pivot > abs(sum)이 될 경우, 바로 아래에도 pivot = abs(sum)으로 해줬어야 했다.

 

 

#include<bits/stdc++.h>

using namespace std;

int n, l, r, pivot = INT32_MAX;
vector<int> v;

void Update(int sum, int L, int R)
{
    if (abs(pivot) > abs(sum)) {
        pivot = sum;
        l = L;
        r = R;
    }
}

void bt()
{
    int L = 0;
    int R = v.size() - 1;

    while (L < R)
    {
        int mid = (L + R) >> 1;
        int sum = v[L] + v[R];

        Update(sum, L, R);

        if (sum == 0) return;
        else if (sum < 0) ++L;
        else if (sum > 0) --R;
    }
}

int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin);
    cin.tie(0);

    scanf("%d", &n);

    int w;
    for (int i = 0; i < n; i++) {
        scanf("%d", &w);
        v.push_back(w);
    }

    bt();

    printf("%d %d\n", v[l], v[r]);

    return 0;
}