[백준 3273/C++] 두 수의 합

1. 문제

 

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

3273번: 두 수의 합

---

2. 문제풀이

#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)

using namespace std;

int n, x, cnt;
int num[100005];
int arr[2000005];

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
		arr[num[i]]++;
	}
	cin >> x;
	for (int i = 0; i < n; i++) {
		arr[num[i]]--; // 중복방지
		if (x > num[i] && arr[x - num[i]] > 0) {
			cnt++;
		}
	}
	cout << cnt;
}

---

3. 문제 평가 및 해설

 

당연한 이야기이지만, 이중 for문으로 하면 시간초과로 오답이 된다. 처음에 나도 이중 for 문으로 시도했다.

#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)

using namespace std;

int n;
int x;
int ans;
int arr[100005];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	cin >> x;

	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			if (arr[i] + arr[j] == x)
				ans++;
		}
	}

	cout << ans;
}

 

위 코드로 시간초과가 났다. 컴퓨터는 보통 2억~3억번의 연산을 1초에 수행하는데, 이 문제는 시간제한이 1초이다. 이중 for문으로 문제를 풀면 시간 복잡도가 O(n^2)이 나오기 때문에, 만약 n이 100000 이라면, 10000000000번의 연산을 수행하므로, 시간초과가 날 수 밖에 없다.

 

따라서 이 문제는 O(n)로 문제를 해결해야한다. 나는 다음과 같은 방법으로 O(n)으로 문제를 해결했다.

 

1. 100000개의 배열을 만든뒤, 배열 내 숫자에 해당하는 인덱스의 값에 1씩 증가시켜준다.

 

2. 배열을 for문으로 n번 순회하면서, 뺄셈을 이용해 인덱스에 접근한 뒤, 0보다 큰 숫자가 들어있으면 cnt을 올려준다.

 

말로 설명하니까 어렵다... 코드로 보면서 이해하는 것이 좋을 것 같다.

 

TC를 보면서 도움을 많이 받았다! 만약 풀이가 맞다고 생각하는데, 계속해서 "틀렸습니다!" 벽에 막힌다면 다음 사이트를 참고하면 좋을 것 같다!

 

https://www.acmicpc.net/board/view/104485