[백준/C++] 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 <bits/stdc++.h>
using namespace std;

int n, a[100000], x, tmp[1000001], ans = 0;
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

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

    /* 틀렸던 코드
    for (int i = 0; i < n; i++) {
        tmp[a[i]] = 1;
		if (x - a[i] > 0 && x - a[i] <= 1000000 && tmp[x - a[i]]) ans++;
    }
    */
    
	for (int i = 0; i < n; i++) {
		if (x - a[i] > 0 && x - a[i] <= 1000000 && tmp[x - a[i]]) ans++;
	    tmp[a[i]] = 1;
    }

	cout << ans;
}

변수 n에 수열의 크기를 입력받고, 배열 a에 인덱스 0번부터 차례로 수열의 값을 입력받는다.

1 ≤ 수열의 크기 ≤ 100000 이므로 배열의 크기를 1000000으로 선언했다. 

(0번지부터 사용하기 때문에 999999로 해도 상관없을 것 같다.)

 

ai + aj = x를 만족하는 쌍을 찾기 위해 x값을 입력받는다.

x에서 ai를 뺐을 때 나오는 값이 배열에 있는지 확인한다. x-ai 값이 배열에 존재한다면 ans에 1씩 더해준다.

 

그렇다면 x-ai 값이 배열 a에 있는지 어떻게 확인할 수 있을까?

배열을 처음부터 끝까지 돌면서 확인하게 되면 중첩 반복문때문에 시간복잡도가 O(n^2)이 되어 시간 초과가 발생한다.

따라서 배열 tmp를 선언해 tmp[ai]값에 1을 넣어주는 방식으로 값의 존재 여부를 저장한다.

 

ai가 x보다 크거나 같은 경우, 그리고  x-ai가 1000001보다 커서 배열 tmp 의 범위를 넘는 경우를 제외시킨다.

(정답 코드에서는 x-ai가 1000001보다 큰 경우를 제외시키기 싫어서 tmp의 크기를 2000001로 선언했다.)

 

그럼 주석에 있는 내 코드가 틀린 이유가 뭘까?

바로 x - ai == ai 인 경우를 고려하지 못했기 때문이다.

tmp 배열에 ai의 존재여부를 먼저 저장한 이후 tmp[x - ai] 값을 확인하기 때문에 자기 자신을 쌍으로 인식할 수 있다.

따라서 tmp[x - ai] 값을 확인한 이후에 tmp[ai]값을 바꿔줘야한다.

 

문제 출처: 3273번: 두 수의 합 (acmicpc.net)

3273번: 두 수의 합