[BOJ] 백준 3273번 두 수의 합

링크

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)

출력

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

풀이

// 두 수의 합
#include <iostream>
using namespace std;


int n, x;
int arr[100005] = {};
// 각 자연수의 존재 여부를 저장하는 배열, 아래에서 x-a[i]가 1000000보다 큰 경우를 예외처리하기 싫어서 그냥 배열을
//  최대 200만으로 잡음
// x - arr[i]의 값을 인덱스로 보고 
// pairIndexArr[]에 0 or 1 bool type카운트를 한다. 
//main안에서 선언하면 크기 초과 에러 발생 -> 전역변수
bool pairIndexArr[2000001];


int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	cin >> x; 
	int cnt = 0 ; 
	
	for (int i = 0; i < n; i++) {
		// x보다 작고 짝이 있나요? 
		if (x > arr[i] && pairIndexArr[x - arr[i]])
			cnt++;
		pairIndexArr[arr[i]] = true;
	}
	cout << cnt ;
}

설명

x - arr[i]의 값을 인덱스로 보고 pairIndexArr[]에 0 or 1 bool type카운트를 한다. 각 자연수의 존재 여부를 저장하는 배열.
main안에서 선언하면 크기 초과 에러 발생 -> 전역변수선언함.

공간복잡도 O(2000000), 시간복잡도 O(n)에 풀이가 가능. 만약 입력 형식에서 x가 a 배열보다 먼저 주어졌다면 int a[] 배열은 필요가 없었음.