[BOJ 3273] 두 수의 합(C++)

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

 

문제

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

 

입력

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

 

출력

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

 

풀이

입력 받은 배열을 정렬 후에 투포인터를 활용한다.

서로 다른 양의 정수이기 때문에 음수와 0이 존재하지 않고 이전의 값보다 다음 값이 항상 크다는 점을 이용해서 시작점을 가장 처음의 수로 끝점을 가장 마지막 수로 설정한다.

left와 right의 합이 x보다 작다면 left를 증가시켜 합을 키운다.

left와 right의 합이 x보다 크다면 right를 감소시켜 합을 줄인다.

left와 right의 합이 x가 된다면 쌍의 개수를 증가시키고 left를 증가시킨다.

left와 right가 같아지거나 left가 right보다 커질 때까지 반복하면서 값을 계속 확인한다.

 

코드

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

int main() {
    int n, num, target;
    vector<int> v;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());

    cin >> target;

    int left = 0;
    int right = n - 1;
    int result = 0;

    while (left < right) {
        int sum = v[left] + v[right];

        if (sum > target) {
            right--;
        }
        else if (sum < target) {
            left++;
        }
        else {
            left++;
            result++;
        }
    }

    cout << result << "\n";
    return 0;
}