[ C++ ] #3273 ( 두 수의 합 )

 

한번 동적할당을 하고 이중 포문을 이용해서 코드를 짰는데

시간초과가 났다..

그래서 두번 공적할당을 하고 합을 구하는 과정에서 시간복잡도를 줄였다..

 

#include <iostream>
#include <algorithm>

using namespace std;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(nullptr);

	int num ;
	int* arr;
	
	cin >> num;
	arr = new  int[num];

	for (int i = 0; i < num; i++) cin >> arr[i];

	int sum=10,fre=0;
	cin >> sum;

	int* N = new  int[sum+1];

	for (int i = 0; i < sum+1; i++) N[i] = 0;

	for (int i = 0; i < num; i++) {
		if (sum >= arr[i]) {
			if (N[sum - arr[i]]) fre++;
			N[arr[i]]++;
		}
	}

	cout << fre;
    
	delete[] N;
	delete[] arr;
}