[백준 C++] 2470. 두 용액

문제 링크

---

2470번: 두 용액

접근 방법

---

서로 다른 정수이므로 정렬을 한 후, 정렬한 수열의 양 끝에서부터 두 수의 합이 최솟값인지 확인합니다.

소스 코드

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#define ABS(x) ((x) > 0 ? (x) : -(x))

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n, s, e, tmp, minRst = INT_MAX, a, b;
    cin >> n;

    vector<int> num(n);
    for (auto &a : num)
        cin >> a;
    
    sort(num.begin(), num.end());
    s = 0;
    e = n - 1;

    while (s < e)
    {
        tmp = num[s] + num[e];

        if (minRst > ABS(tmp)) // 최솟값일 때
        {
            minRst = ABS(tmp);
            a = num[s];
            b = num[e];

            if (!tmp) // 0 이면 더 작을 수 없으므로 종료한다.
                break;
        }

        if (tmp > 0) // 0 보다 크면 e를 감소
            --e;

        else // 0 보다 작으면 s를 증가
            ++s;
    }

    cout << a << ' ' << b;

    return 0;
}

코드 설명

---

n이 최대 100,000 이므로 이중 for 문으로 두 수의 합을 구하게 된다면 n²이기 때문에 10,000,000,000번의 연산을 하게 됩니다. 대략 1억 번의 연산이 1초이므로 이중 for문으로는 풀지 못함을 알 수 있습니다.

따라서 정렬을 한 후, 먼저 시작 인덱스(s)의 수와 끝 인덱스(e)의 수를 더한 다음, 0 보다 크면 e를 감소시키고, 0보다 작다면 s를 증가시킵니다.

유사 문제

---

[백준 C++] 3273. 두 수의 합