[백준] 3273 두 수의 합 (C++)

작성일 Edited on In , Views: Disqus:

문제

원문 링크 : https://www.acmicpc.net/problem/3273

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

풀이 및 구현

문제를 풀기 위해 투 포인터 알고리즘을 사용했다.

문제에서 주어진 수열을 우선 오름차순으로 정렬한다.
$$5, 12, 7, 10, 9, 1, 2, 3, 11 \rightarrow 1, 2, 3, 5, 7, 9, 10, 11, 12$$
수열의 왼쪽 끝을 가르키는 $l$과 수열의 오른쪽 끝을 가르키는 $r$을 만든다.

두 인덱스가 가르키는 원소를 더했을 때 나올 수 있는 경우의 수는 아래와 같다.

$$1. v[l] + v[r] < x$$
$$2. v[l] + v[r] > x$$
$$3. v[l] + v[r] = x$$

1번은 현재 목표 값보다 합이 작기 때문에 $l$포인터를 증가시켜 합을 크게 만든다.

2번은 현재 목표 값보다 합이 크기 때문에 $r$포인터를 감소시켜 합을 작게 만든다.

3번일 때 현재 목표 값과 동일하므로 $(a_i, a_j)$에 추가한다.
이 때 수열의 값은 모두 다르기 때문에 $v[l]$과 $v[r]$ 둘 중 하나를 이용해서 새롭게 $x$를 만들어 낼 수 없다.
그러므로 $l$포인터는 증가시키고 $r$포인터는 감소시켜 새로운 순서쌍을 찾을 수 있게 한다.

위 과정을 $l$포인터가 $r$포인터보다 작을 때까지 반복하면서 순서쌍의 개수를 세주면 문제를 해결할 수 있다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>  
#include <vector>  
#include <algorithm>  
using namespace std;  
   
int main() {  
    ios_base::sync_with_stdio(false);  
    cin.tie(nullptr); cout.tie(nullptr);  
   
    int n, x;  
    cin >> n;  
   
    vector<int> v(n);  
    for (auto& i : v) cin >> i;  
    sort(v.begin(), v.end());  
    cin >> x;  
   
    int l = 0, r = n - 1, cnt = 0;  
    while (l < r) {  
        int sum = v[l] + v[r];  
        if (sum <= x) l++;  
        if (sum >= x) r--;  
        if (sum == x) cnt++;  
    }  
    cout << cnt;  
}

후기


바로 먼저 투 포인터가 생각나서 투 포인터로 풀었다.
이외에도 이분 탐색을 사용해서 풀 수도 있을 것이고
$a_i$의 범위가 $1\leq a_i \leq 1000000$이므로 $a_i$에 대해 $x-a_i$가 존재하는지 찾아본다면
정렬이 필요하지 않으므로 $O(n)$으로도 풀 수 있을 것이다.