백준 2295번 세 수의 합(C++)

 어려운 문제였다. 문제를 잘 읽고 분석하는게 참 중요했던 문제. 이런 문제도 있구나 세상은 넓고 나는 너무 ㅈ밥이다.... 

처음 생각한 풀이:

1. nC3 조합을 구함

2. 집합에 속하면 삽입

3. answer를 max로 갱신

 

-> 시간초과. 

 

 이 문제는 완탐을 해야하는데 그 도구가 DFS 조합이었다. 그러나 N이 클 때는 오버헤드 문제를 고려하여 반복문 BF보다 조합이 훨신 느리다. 시간복잡도는 O(2^100 * N^M)

 

두 번째로 생각한 풀이:

1. BF로 모든 값을 구함

2. 벡터에 삽입

3. 주어진 집합을 sort

4. 주어진 집합의 최대값부터 이분탐색

5. 큰 값부터 찾으니 존재하면 출력 후 종료

 

이것도 틀렸다. 우선 3개를 고르기 때문에 기본적으로 O(N^3)의 시간이 걸리니 이분탐색까지 하면 O(N^3 * logN) N은 1000이므로 시간초과이다.

 

결국 구글신의 도움을 받았다. 문제의 핵심은 결국은 모두가 집합에 속하는 원소들이라는 사실이다. 

 

즉.

 

a + b + c = k  이것을 다시 쓰면 element[i] + element[j] + element[k] = element[t] 이고

element[i] + element[j] = element[t] - element[k] 

 

이므로 두 개의 합만 구하고 이분탐색하면 

O(N^2 * logN) 의 시간으로 구할 수 있고 이게 정답이다. 1000 1000 * 10 = 10000000 

 

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

int N;
int answer = -1;
vector<int> element;
vector<int> result;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		element.push_back(tmp);
	}

	sort(element.begin(), element.end());

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
				result.push_back(element[i] + element[j]);
		}
	}


	sort(result.begin(), result.end());

	for (int i = N - 1; i > -1; i--) {
		for (int j = i; j > -1; j--) {
			if (binary_search(result.begin(), result.end(), element[i] - element[j])) {
				cout << element[i];
				return 0;
			}
		}
	}
}

 

후,,,,