[알고리즘] 용액

구현 방식

• 제한 시간이 1초이고 N이 100000 이하의 수 이므로 O(N^2) 이하의 코드를 짜야한다.
• N개의 용액에서 0번째부터 N-1개까지 순차적으로 하나 선택한 용액 k 와 k+1 ~ N-1 번째까지의 용액 중에 가장 절대값을 최소로 하는 용액을 이분탐색을 통해 찾아낸다.
• 그렇게 하면 O(N * log (N - k)) 이므로 시간 제한에 걸리지 않을것이다.
• 여기서 이분탐색할 때, sum == 0 으로 지표를 나누기 때문에 수렴하는 부분이 최소 합을 가지는 게 아닐수도 있다.
• 최소값을 저장하는 변수를 따로 만들어서 리턴해주자.

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>

using namespace std;

void solution(int N, const vector<long long> &v);
pair<long long, long long> binarySearch(long long number, int minIdx, int maxIdx, const vector<long long> &v);

int main()
{
    int N;
    cin >> N;
    vector<long long> v(N);
    for (int i = 0; i < N; i++) cin >> v[i];

    solution(N, v);
}

void solution(int N, const vector<long long> &v)
{
    long long sumMin = LLONG_MAX;
    pair<long long, long long> result = make_pair(-1, -1);

    for (int i = 0; i < N; i++)
    {
        auto p = binarySearch(v[i], i + 1, N - 1, v);
        auto addNumber = p.first;
        auto sum = abs(p.second);
        if (sumMin > sum)
        {
            result = {v[i], addNumber};
            sumMin = sum;
        }
    }

    cout << result.first << " " << result.second;

}


pair<long long, long long> binarySearch(long long number, int minIdx, int maxIdx, const vector<long long> &v)
{
    long long sumMin = LLONG_MAX;
    pair<long long, long long> result = {-1, sumMin};

    int midIdx = (minIdx + maxIdx) / 2;
    long long sum = LLONG_MAX;
    while (minIdx <= maxIdx)
    {
        midIdx = (minIdx + maxIdx) / 2;
        sum = number + v[midIdx];

        if(sumMin > abs(sum))
        {
            sumMin = abs(sum);
            result = {v[midIdx], sum};
        }

        if (sum == 0) break;
        else if (sum > 0) maxIdx = midIdx - 1;
        else minIdx = midIdx + 1;
    }

    return result;
}