3273 - 두 수의 합

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

C++

1#include <bits/stdc++.h>
2using namespace std;
3
4int main(void) {
5  ios::sync_with_stdio(0);
6  cin.tie(0);
7
8  int n, x, t, cnt=0;
9  vector<int> a;
10  scanf("%d", &n);
11  for(int i=0; i<n; ++i) {
12    scanf("%d", &t);
13    a.push_back(t);
14  }
15  scanf("%d", &x);
16
17  // O(n log n)
18  sort(a.begin(), a.end());
19
20  // O(n^2)
21  for(int i=0; i<n-1; ++i) {
22    for(int j=i+1; j<n; ++j) {
23      if(a[i] + a[j] == x) ++cnt;
24      else if(a[i] + a[j] > x) break;
25    }
26  }
27
28  printf("%d\n", cnt);
29  return 0;
30}