문제 출처

  • 풀이법이 굉장히 신기해서 가져온 문제이다.
  • 요즘 Bakingdog 님의 저지를 풀고 있다..

1. 문제설명

  • n개의 서로 다른 양의 정수로 이뤄진 수열이 있다.
  • $a_i + a_j$=x를 만족하는 쌍의 수를 구하라.



2. 알고리즘 설계

  • $O(N^2)$으로 접근하면 무조건 시간초과이다.
  • i번째 수를 x에서 뺐을 때 그 수가 입력되었는지 확인하면된다!



3. 로직

  • 코드
    • N번의 접근으로 수열을 구할 수가 있다.
int arr[2000000];
for(int i=0; i<n; i++)
  if(arr[x-arr[i]] > 0) ans++;



4. 전체 코드

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

int n, x, arr[2000001], ans;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for (int tmp, i = 0; i < n; i++) {
		cin >> tmp;
		arr[tmp]++;
	}
	cin >> x;

	for (int i = 0; i < (x + 1) / 2; i++)
		if (arr[i] == 1 && arr[x - i] == 1)
			ans++;

	cout << ans;
	return 0;
}