[백준] 3273 : 두 수의 합

www.acmicpc.net/problem/3273

3273번: 두 수의 합

---

• 들어오는 값들을 정렬 후, 양쪽 끝에서 비교해가며 움직인다.
• 왼쪽은 작은값에서 올라가고, 오른쪽은 큰 값에서 내려가는 방식이다.
• 현재 왼쪽과 오른쪽 값의 합을 기준으로 했을 때, 목표값보다 클 경우엔 값을 낮춰야 하기 때문에 오른쪽 포인터를 이동시켜 값을 작게 만들어준다.
• 마찬가지로 목표값보다 작을 경우는 왼쪽을 움직여 크게 만들어주는 방식을 반복하면, O(n) 에 비교가 가능하다.

---

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

using namespace std;

int n, x, item, cnt;
int ldx, rdx;
vector<int> v;

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 0 ; i < n ; i++)
    {
        cin >> item;
        v.push_back(item);          // 배열 전부 입력받은 후
    }
    cin >> x;
    sort(v.begin(), v.end());       // 오름차순으로 정렬

    ldx = 0;
    rdx = v.size()-1;               // 양 끝점부터 시작
    while(ldx < rdx)                // 원소 다 돌때까지
    {
        item = v[ldx] + v[rdx];     // 두 수의 합이
        if(item < x) ldx++;         // 작다면 왼쪽포인터를 옮겨 값을 키우고
        else if(item > x) rdx--;    // 크다면 오른쪽을 내려 값을 줄이고
        else
        {
            cnt++;                  // 구하는 값과 같다면 카운트해주고 오른쪽을 내림
            rdx--;
        }
    }

    cout << cnt << endl;
}