BOJ 2467 - 용액

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

 

투포인터로 풀었다.

 

처음문제를 봤을때는 이걸 어떻게 해야하나, preSum을 구해야하나, 값을 입력받을때마다 0번인덱스와 더한값 저장, 1번인덱스와 더한값저장 이렇게 해야하나,,, 고민했다.

그런데 그러기에는 숫자가 너무 컸다. N이 일단 100,000까지니깐 이렇게 하면 무조건 시간복잡도가 초과되었다. 

문제를 다시 읽어보니 특성값이 -1,000,000,000부터 1,000,000,000까지였고 정렬되서 주어진다고 했다.

값도 너무 크고, 정렬이라는 단어가 있으니 여기서 이분탐색을 떠올렸다.

그러면 이제 이분탐색을 어떻게 해야할까... 이분탐색은 보통 시작과 끝을 더하고 그걸 2로 나눈 중간값을 구해서 그 중간값과 특정값을 비교하고 이걸 기반으로 시작값과 끝값을 조정해 다시 중간값을 구하고... 이걸 반복하는데...

음 그런데 여기서는 중간값의 절대값이 최대한 0에 가깝게 가야한다.

 

근데 문제에서는 두 값을 더한값이 0에 가까운 수를 구하라고 했으니, 굳이 2로 나눠줄 필요없이, 수 두개를 더해주기만 하면 된다.

=> 투포인터를 쓰자. 이런식으로 의식의 흐름이 흘렀고 (물론 약간 꾸며낸 부분이 있다) 투포인터를 사용하기로 했다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> a;
ll n;
ll num;
ll mn = 1e11;
pair<ll, ll> ans;
int main()
{
    cin >> n;
    for (ll i = 0; i < n; i++)
    {
        cin >> num;
        a.push_back(num);
    }

    ll l = 0;
    ll r = a.size() - 1;
    while (l < r)
    {
        ll sum = abs(a[l] + a[r]);
        if (sum < mn)
        {
            mn = sum;
            ans = {a[l], a[r]};
            l++;
        }
        else
        {
            r--;
        }
    }

    cout << ans.first << " " << ans.second << "\n";

    return 0;
}

 

처음에는 이렇게 풀었는데 틀렸습니다가 나왔다.

왜그러냐면 sum의 절대값을 mn이랑 비교해서 더 작을경우 처리를 해줬기 때문이다.

물론 절대값을 씌우면 작을수록 0에 가까워지긴 하지만, 수의 범위가 마이너스부터 이기때문에, 저렇게 될 경우

-10 0 100 200 일 때, 처음에 -10 과 200을 더하고나서 left를 올려줘서, 그 다음 0과 200을 더해주고 이런식으로 진행해나가게 된다.

(반례 얻은곳 : https://www.acmicpc.net/board/view/138333 )

 

따라서 0에 점점 더 가까워 지려면 더한 값이 0보다 작다면, -값이 더 커져야 하므로 left가 ++되야하고, 0보다 크다면 +인 값이 더 작아져야 하므로 right를 --해야 한다고 생각했다. 그리고 그중에 절대값 sum이 가장 작은값을 정답으로 해주면 된다고 생각했다. 이렇게 구현했고, 답을 맞출 수 있었다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> a;
ll n;
ll num;
ll mn = 1e11;
pair<ll, ll> ans;
int main()
{
    cin >> n;
    for (ll i = 0; i < n; i++)
    {
        cin >> num;
        a.push_back(num);
    }

    ll l = 0;
    ll r = a.size() - 1;
    while (l < r)
    {
        ll sum = a[l] + a[r];

        if (abs(sum) < mn)
        {
            mn = abs(sum);
            ans = {a[l], a[r]};
        }

        if (sum < 0)
        {
            l++;
        }
        else
        {
            r--;
        }
    }

    cout << ans.first << " " << ans.second << "\n";

    return 0;
}

/*
4
-10 0 100 200

ans : -10 0
*/

 

 

재밌었다.