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

문제

접근 방법

맵, 이분 탐색 등 여러 가지가 생각났지만 서로 다른 양의 정수라는 점에서 양옆에서 접근하는 방식으로 해결할 수 있을 거 같았다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, x, startIndex, endIndex, cnt;
vector<int> a;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    a = vector<int>(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    cin >> x;
    sort(a.begin(), a.end());
    endIndex = n - 1;
    while (startIndex < endIndex)
    {
        int sum = a[startIndex] + a[endIndex];
        if (sum == x) // 같다면 두 값 모두 사용 불가 (서로 다른 정수이므로)
        {
            ++cnt;
            ++startIndex;
            --endIndex;
        }
        else if (sum > x) // 합이 높다면 값 줄이기
            --endIndex;
        else // 작다면 값 높이기
            ++startIndex;
    }
    cout << cnt;
    return 0;
}

풀이

100000이기에 n^2은 힘들다.
굳이 이분 탐색으로 수를 찾는 것보단 양옆에 수를 탈락시켜 가면서 값을 찾는 것이 더 좋은 풀이인 것 같다.