(C++) [백준 3273번] 두 수의 합

https://www.acmicpc.net/problem/3273

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)

출력

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

예제 입력 1 복사

9
5 12 7 10 9 1 2 3 11
13

예제 출력 1 복사

3

 

1000000 이하의 서로 다른 자연수 수열이 있고 어떤 자연수 x가 주어졌을때 수열 내의 두 수의 합이 x가 되는 개수를 출력하는 문제이다.

x는 200만 이하이고 수열의 크기는 10만, 수열 내 값의 크기는 모두 100만 이하이다.

 

직관적으로 떠오르는 풀이는 수열의 첫 번째 값부터 n-1번째까지 각각 비교해보는 O(N^2) 풀이인데 n이 10만이므로 이 문제에서는 써먹을 수가 없다.

 

바킹독님의 강의에서 비슷한 문제를 O(N)에 풀었던 기억이 나고, 이 문제도 카운팅을 사용하면 좋을 것 같다는 생각이 들어서 비슷하게 짜보기로 했다.

내가 구현한 방법은 다음과 같다.

1. 수열을 담을 배열 Num[100005], 카운팅 할 배열 Cnt[2000005] 선언하기: 200만인 이유는 뒤에 설명하겠다.

2.

for (int i=0; i<n; i++)
	if(Cnt[x-Num[i]] == 1) res++;

수열을 n까지 돌리면서 Cnt[x-Num[i]]이 1이면(카운팅이 됐으면) res 변수를 1 더한다.

이 문제는 수열의 임의의 두 수 ai,aj가 x가 되는, 다시 말해서 ai + aj == x인 수를 찾는 문제인데 x - aj == ai임을 찾아도 무방하고, Num[i]를 aj라고 생각해보면 x-Num[i]는 ai가 된다. 즉 Cnt[x-Num[i]]는 ai번째 수가 등장했는지 여부를 확인해준다고 볼 수 있고 1이면 등장했으므로 값을 추가하게 된다.

그런데 이렇게 코드를 짜면 인덱스 범위에 문제가 발생한다. 왜냐면 x가 충분히 작은 값이고 Num[i]가 크다면 인덱스의 -를 참조하게 되고, 이는 배열의 - 인덱스를 참조하게 되기 때문이다.

따라서 코드를 아래와 같이 바꿔주어야 한다.

for (int i=0; i<n; i++){
	if(x-Num[i] >= 0 && Cnt[x-Num[i]] == 1) res++;}

이렇게 하면 x-Num[i]이 음수일 때는 바로 통과하기 때문에 문제가 발생하지 않는다.

Cnt가 200만인 이유는 x가 150만정도의 큰 수고 Num[i]가 1일 때 Cnt가 100만이라면 마찬가지로 인덱스 범위가 초과되는 일이 발생하기 때문이다.

그리고 res를 리턴하면 되는데 이 때 조심해야 할 부분이 있다.

예외적으로 2가지를 처리해줘야 하는데 먼저 res는 /2로 나눈 값을 전달해야 한다.

중복처리를 하는 방법도 있을 수 있지만 나는 중복처리를 따로 해주지 않았기 때문에 ai와 aj의 위치가 바뀌었을때 2번 값을 계산하기 때문에, /2로 나누어주어야 한다.

그리고 답이 1인 경우가 있다.

1

1

2와 같은 경우인데, ai와 aj가 같은 인덱스여도 성립하므로 res는 1이 되는데 1/2는 0으로 계산되므로 문제가 발생할 수 있다.

따라서 리턴부분 코드를 아래와 같이 작성해주어야 한다.

if(res == 1) return res;
else return res/2;

 

전체 코드는 다음과 같다.

#include <iostream>
using namespace std;
int x, n;
int num[100005], cnt[2000005];
void input()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> num[i];
		cnt[num[i]]++;
	}
	cin >> x;
}
int solve()
{
	int res = 0;
	for (int i = 0; i < n; i++)
	{
		if (x - num[i] < 0) continue;
		if (cnt[x - num[i]] == 1) res++;
	}
	if (res == 1) return res;
	else return res / 2;
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	input();
	cout << solve();
}