(백준 c++)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)

출력

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

 

투 포인터 알고리즘.

 

n개의 수를 v 벡터에 담아 저장한다.

v를 오름차순으로 정렬한 후 투 포인터 시작.

start = 0, end = n - 1로 시작을 한다.

 

start < end 일 때까지 반복.

start와 end에 해당하는 두 수의 합이 X와 같다면 answer++, start++을 해준다.

만약 두 수의 합이 X보다 작다면 end--,

X보다 크다면 end--를 해준다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
    int n, X, answer = 0;
    int start = 0, end = 0;

    cin >> n;

    vector<int> v(n, 0);

    for(int i = 0; i < n; i++){
        cin >> v[i];
    }

    sort(v.begin(), v.end());

    end = v.size() - 1;

    cin >> X;

    while(start < end){
        int sum = v[start] + v[end];

        if(sum == X){
            answer++;
            start++;
        }
        else if(sum < X){
            start++;
        }
        else{
            end--;
        }
    }

    cout << answer;
    
    return 0;
}