3273번-두 수의 합

#include<bits/stdc++.h>
using namespace std;

int num[100000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, a, x, cnt = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		num[i] = a;
	}
	cin >> x;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			if (num[i]+num[j]==x){
				cnt += 1;
			}
		}
	}
	cout << cnt;
}

위의 코드로 풀었더니 시간초과가 나왔다. 당연히 이중 for문이면 O(n^2)이니 주저했어야했는데 c++의 빠른 채점 속도에 잠시 안일했다..ㅎ

 

#include<bits/stdc++.h>
using namespace std;

int arr[100000];
bool exist[2000000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, x, cnt = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		exist[arr[i]] = true;
	}
	cin >> x;
	for (int i = 0; i < n; i++) {
		if (x - arr[i] > 0 && exist[x - arr[i]]) {
			cnt += 1;
		}
	}
	
	cout << cnt/2;
}

내가 수정해서 제출한 풀이이다. 

아래는 아이디어는 같지만 x의 합을 갖는 쌍의 수를 세는 방법이 조금 달라서 첨부한다. 

#include <bits/stdc++.h>
using namespace std;

int a[1000001]={};
// 각 자연수의 존재 여부를 저장하는 배열, 아래에서 x-a[i]가 1000000보다 큰 경우를 예외처리하기 싫어서 그냥 배열을 최대 200만으로 잡음
bool occur[2000001];
int n, x;

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

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

  for (int i = 0; i < n; i++) {
    // x-a[i]가 존재하는지 확인
    if(x-a[i] > 0 && occur[x-a[i]]) ans++;
    occur[a[i]] = true;
  }
  cout << ans;
}