[BOJ/3273/C++] 두 수의 합

출처: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)

SOL

두 수의 합이 N과 같은 쌍을 찾는 문제이다. 이것도 2중반복문으로 가능하지만, 해당 문제는 10^10이 되므로, 2중반복문은 안된다. 즉, 다른 방법을 찾아야함.

A = {1,2,3,4,5} 가 있다고 하고, 두 수의 합이 6인 쌍의 갯수를 보자.

이때, 관점을 조금 바꿔서, 1과 합쳐서 6이되는 숫자는 "5"이므로, 해당 배열에 5가 있는지 없는지 보면된다. 즉, 방문배열을 만들어서, 각 숫자와 합해서 원하는 숫자 X가 되는지 확인하면 된다.
예를들어, 위 같은 경우는 vistied = [0,0,0,0,0,0] 이 있다면, 1,2,3,4,5을 반복돌면서 방문배열을 체크하면된다.

첫번째 반복
visited[5] = 0이므로 1은 합이 6인게 없다고 생각하고, 1은 체크한다.
두번째 반복
visited[4] =0이므로, 2는 합이 6인게 없다고 생각하고 2를 체크한다.
...

4는 visited[2]가 1이므로, 합이 6인 쌍이 있다.
마찬가지로 5는 visited[1] =1이므로, 합이 6인 쌍이 있다.

이때, X-number가 음수일 수 있기 때문에, 예외 처리를 해주어야한다.

#include <bits/stdc++.h>
using namespace std;

bool arr[2000001] = {};
int number[1000001] = {};

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  int N, X;
  int cnt = 0;
  cin >> N;
  for (int i = 0; i < N; i++)
    cin >> number[i];
  cin >> X;
  for (int i = 0; i < N; i++)
  {
    if (X - number[i] > 0 && arr[X - number[i]])
      cnt++;
    arr[number[i]] = true;
  }
  cout << cnt;
  return 0;
}