[백준] 3273번: 두 수의 합

20 Oct 2018

Reading time ~3 minutes

문제

n개의 서로 다른 양의 정수 a₁, a₂, …, a_n으로 이루어진 수열이 있다. a_i의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, a_i + a_j = x (1 ≤ i < j ≤ n)을 만족하는 (a_i, a_j)쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

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

예제

입력

9
5 12 7 10 9 1 2 3 11
13

출력

풀이

단순히 이중 for문을 사용해서 일일히 찾을 수도 있지만 좀더 효율적인 방법으로 구현했다.

먼저 입력 받은 배열을 정렬 후 두 개의 변수 i, j를 두어 i는 앞에서부터 뒤로, j는 뒤에서부터 앞으로 탐색하여 두 수의 합을 x와 비교한다.

만약 두 수의 합이 x보다 크면 합을 줄여야하므로 j를 한 칸 앞으로 줄이고, 반대로 합이 x보다 작으면 합을 증가시켜야하므로 i를 뒤로 한 칸 옮긴다.

두 수의 합이 x와 같을 경우에 count를 증가시킨 후 i와 j를 각각 앞뒤로 한 칸씩 옮긴다. 이 때 둘 다 옮기는 이유는 문제 조건에 따라 배열 안의 숫자들은 모두 서로 다른 양의 정수들이기 때문에, 하나의 숫자는 하나의 쌍에만 포함될 것이기 때문이다. 만약 두 숫자가 조건을 만족하는 쌍이라면 그 숫자들은 다른 쌍에는 사용되지 않을 것이기에 다음 숫자들로 넘어간다.

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

int main() {
    int n;
    int x;
    vector<int> numbers;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        numbers.push_back(temp);
    }
    cin >> x;

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

    int i = 0;
    int j = n - 1;
    int count = 0;

    while (i < j) {
        int sum = numbers[i] + numbers[j];
        if (sum == x) {
            count++;
            i++;
            j--;
        } else if (sum < x) {
            i++;
        } else {
            j--;
        }
    }
    
    cout << count;
    return 0;
}

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