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

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

3273번: 두 수의 합

풀이

 

문제를 보고 2중 for문으로 풀면 되는 것 아닌가? 하셨을 수도 있겠어요.

하지만, 시간 제한이 1초이기 때문에 O(N^2) 풀이로는 시간초과가 발생할 것입니다. (주어진 N의 최대값은 10만이고 1초는 대략 3-5억번의 연산을 수행하기 때문에 당연히 초과)

 

시간복잡도를 줄이기 위해서는 공간복잡도를 희생해보는 건 어떨지 고민해봅시다. (trade-off!)

 

수열의 크기 n을 입력받고 크기가 n인 배열에 다시 요소들을 입력받는 것은 당연하겠죠?

이후 합이 x가 되는 배열의 요소 쌍의 개수를 구하고 싶은 것인데

그럴려면 크기가 n인 배열을 반드시 한 번은 순회해야하는 것도 ok입니다.

 

크기가 x인 배열을 만들고

순회 과정에서 방문 표시를 해주는 것은 어떨까요?

방문표시가 되었다. (== 배열에 이 수가 존재한다)를 이용해 내가 현재 순회 중인 요소 + 방문표시가 된 값 == x를 만족시키면 되겠죠!

x - 내가 현재 순회 중인 요소가 방문표시가 된 값인지 체크하는 코드를 작성하면 되겠네요!

 

방문표시는 요소의 값이 1이 될 때로 합시다.

이 논리를 코드로 구현하면 아래와 같습니다.

(이 때, x가 배열의 요소보다 반드시 크다는 조건이 문제에서 주어지지 않았어요.)

 

 

코드

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


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int cnt = 0;
	int n;
	cin >> n;
	vector<int>v1(n);
	for (auto& i : v1)
		cin >> i;
	int x;
	cin >> x;
	vector<int>v2(x,0);
	for (int i = 0; i < v1.size(); i++) {
		if (x > v1[i] && v2[x - v1[i]]) // x > v1[i] 조건에 유의합시다! 런타임에러가 날 수 있어요
			cnt++;
		else if (x > v1[i])
			v2[v1[i]] = 1;
	}
	cout << cnt;
}

 

 

vector을 쓰지 않고 배열로 푼다면

 

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/fc842a288ef843e49e2fe5b6a8bbcf5e
#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;
}

/*
공간복잡도 O(2000000), 시간복잡도 O(n)에 풀이가 가능. 만약 입력 형식에서
x가 a 배열보다 먼저 주어졌다면 int a[] 배열은 필요가 없었음.
*/

+ x가 a 배열보다 먼저 주어졌다면 int a[] 배열은 필요가 없다는 것이 무슨 뜻일까요?