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

문제링크

3273번: 두 수의 합

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

 

풀이

데이터의 수가 많기 때문에 이분 탐색을 이용하여 풀이하였다.

입력 받은 수열을 오름차순으로 정렬한 뒤 각 항마다 이분 탐색을 통하여 X를 만들 수 있는 수가 존재하는지 판단하여 개수를 세어준다.

나의 경우에는 배열의 index를 이분 탐색을 통해 찾았다. 

같은 항이 두 번 사용되면 안되기 때문에 해당 처리를 해주는 것이 중요한 부분인 것 같다.

ex)

5

1 2 3 4 5

6

→ (1, 5), (2,4) 만 가능하지만 위의 처리를 해주지 않으면 (3, 3)도 포함되어 3개가 나올 수 있다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, x, result;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    cin >> x;
 
    // 오름차순 정렬
    sort(v.begin(), v.end());
 
    // 각 항마다 이분 탐색 -> aj의 j를 찾는다.(index)
    for (int i = 0; i < n - 1; i++) {
        int searchNum = x - v[i];    // 찾는 수
        int left = i;
        int right = n - 1;
        int mid = 0;
 
        while (left <= right) {
            mid = (left + right) / 2;
 
            if (searchNum < v[mid]) {
                right = mid - 1;
            }
            else if (searchNum > v[mid]) {
                left = mid + 1;
            }
            // 같다면 stop
            else {
                break;
            }
        }
        
        if (mid >= n) {
            continue;
        }
 
        // mid 와 i가 같으면 같은 항이 두 번 사용될 수 있기 때문에 제외해줘야 한다.
        if (v[mid] == searchNum && mid != i) {
            result++;
        }
    }
 
    cout << result;
}