[BOJ/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)

출력

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

풀이 아이디어

- 입력된 숫자들을 배열에 담는다

- 합으로 나올 수 있는 최대 값 크기만큼 bool array를 만든다.

- O(N)에 문제를 풀고,  ai+aj=x가 있는지 확인하기 위해  for문을 돌면서 bool array에 값이 있고, 합-vector 원소가 >0 인지를 확인한다.

- 만약에 합이되는 수가 있다면 arr[x-vec[i]] == true고, x-vec[i]역시 >0 이므로 해당 조건문에 들어가게되어 카운트를 ++ 할 수 있다.

코드

#include <iostream>
#include <vector>
using namespace std;

bool arr[2000001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, x;
	cin >> n;
	vector <int> vec(n);

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

	for (int i=0; i<vec.size(); i++)
	{
    	int data= vec[i];
		if (x >= data && arr[x - data]) cnt++;
		arr[data] = true;
	}

	cout << cnt << "\n";
}

배운점

처음에는 이중for문으로 만들었다가 시간제한이 1초라서 O(n^)으로 해결하면 안됨을 깨달았다.

 

N이 10만정도일 때 시간복잡도가 O(N)일 경우, 1/1000초 정도에 해결 할 수 있다.

같은 N에서 O(N^2)의 경우 값이 100억이므로 약 100초 정도가 걸리므로 O(N^2)으로 문제를 풀어서는 안된다. 

 

문제를 풀 수록 점차 수행시간을 생각하는 발전이 생긴거같다~~