백준 3273 두 수의 합

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

3273번: 두 수의 합

 

 

EXPLANTION

n개의 숫자를 정렬하고 index 0과 index n-1에 포인터를 둔다.

각 index의 원소의 합이 x보다 크면 뒤에 있는 포인터의 index를 하나 내리고,

작으면, 앞에 있는 포인터 index를 하나 올린다.

이를 투 포인터가 교차할 때까지 반복하면서 두 포인터가 가리키는 원소들의 합이 x와 같은 지 판별한다.

두 원소의 합이 같을 때는 앞에 있는 포인터의 index를 하나 올리거나, 뒤에 있는 포인터의 index를 하나 내린다.

 

CODE

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n,x;

int main() {
    cin >> n;
    vector<int> arr;

    for(int i=0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }

    cin >> x;

    int start=0, end= n-1;
    int count = 0;

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

    while(start < end) {
        if(arr[start] + arr[end] == x) {
            count++;
            start++;
        } else if(arr[start] + arr[end] > x) {
            end--;
        } else {
            start++;
        }
    }

    cout << count;
}