[BOJ/C++] 백준 3273번: 두 수의 합

 

🔗 문제 링크 : https://www.acmicpc.net/problem/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)

 

 

출력

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

 

 

 

입출력 예시

 

 

 

---

 

풀이 

수열은 서로 다른 양의 정수로 이루어졌다. -> 중복되는 수가 없다.

(1 ≤ i < j ≤ n)를 만족하므로 i와 j는 같은 값을 가지지 않는다. ->

예를 들어, 1 3 7 5 인 수열에서 합이 10이 되는 쌍으로 (5, 5)가 될 수 없다.

 

투포인터의 대표적인 문제 중 하나다. 

테스트에서 시간 초과가 많이 발생하는데, 해결방법은 아래와 같다.

• 입력으로 받은 수열은 정렬한 상태로 조건을 만족하는 쌍의 개수를 구한다.
• 현재 start와 end의 두 수를 더한 값이 x보다 클 때, 작을 때, 같을 때에 따라 적절한 반복문 탈출과 같은 처리를 해야한다. 

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

int main() {
    ios_base::sync_with_stdio(0);
    int n, x;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    cin >> x;
    sort(nums.begin(), nums.end());
    int end = n - 1;
    int count = 0;
    int sum;
    for (int start = 0; start < n; start++) {
        while (end > start) {
            sum = nums[start] + nums[end];
            if (sum < x) 
                break;
            else if (sum == x) {
                count++;
                break;
            }
            end--;
        }
    }
    cout << count;
}

 

 

 

---