[백준] 3273번: 두 수의 합 (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)

 

 

 

출력 :

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

 

 

 

 

 

 

풀이)

투포인터를 사용하여 문제를 풀어주면 된다.

 

구간이 아닌 두 수의 합이므로 포인터가 옮겨질 때마다, 

 

해당 포인터가 있던 값을 빼고 , 옮겨간 자리의 값을 더해주는 것이 핵심이다.

 

 

#include <iostream>
#include <vector>
#include <sstream>
#include <string>
#include <algorithm>
using namespace std;
 
int main() {
 
    int n;
    cin >> n;
    cin.ignore();
 
    // 문자열 입력받기
    vector<int> v;
    string num;
    string line;
    getline(cin, line);
    stringstream sstream(line);
    while(getline(sstream, num, ' ')) {
        v.push_back(stoi(num));
    }
    
    sort(v.begin(), v.end());
 
    int check;
    cin >> check;
    cin.ignore();
 
    // 투포인터 사용
    int s, cnt = 0;
    int e = n - 1;
    int total = v[s] + v[e];
 
    while (s < e) {
        if(total == check) {
            cnt++;
            total -= v[e];
            e--;
            total += v[e];
        } else if (total < check) {
            total -= v[s];
            s++;
            total += v[s];
        } else {
            total -= v[e];
            e--;
            total += v[e];
        }
    }
 
    cout << cnt;
 
    return 0;
}

 

---

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

3273번: 두 수의 합