백준 28110번 마지막 문제 (C++)

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

28110번: 마지막 문제

 

 문제 자체는 어렵지 않은 구현문제이지만 숫자가 10억으로 매우크다. 그리고 제한시간이 0.5초이기 때문에 O(10억)으로도 풀어낼 수 없다.

처음 생각한 풀어는 이분탐색이었다. 그러나 결정을 해도 더 큰수를 찾아야하는지, 작은수를 찾아야하는지 알 수 없다. 그러므로 풀어낼 수 없다.

 

아무리 생각해도 풀수 없을 것 같아 에디토리얼을 보니 수학적인 문제였다. 

 

2 4 8 에서 2 4 8 모두 보지말고 2 4 두개만보자. 이들과 가장 차이가 크게날 수 있는 수는 이 둘의 등차중항이다. 그러므로 후보가될 수 있는 X = (Ai + Ai+1) / 2 이다. 즉 모든 후보를 보면 안되고 이 X들만 확인해봐야 문제를 풀 수 있다.

 

아무리 생각해도 이런 문제는 못 풀 것 같다. 경험이 답인가.. 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;

	vector<int> prob;
	vector<int> answer;


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

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

	if (prob.size() == prob[prob.size() - 1] - prob[0] + 1) {
		cout << "-1" << '\n';
		return 0;
	}

	for (int idx = 0; idx < N; idx++) {
		int X = 0;
		if (idx != N - 1) {
			X = (prob[idx] + prob[idx + 1]) / 2;		
			answer.push_back(X);
		}
	}

	int mins = -1000000000;
	int ans = -1;
	for (auto an : answer) {
		int min = 1000000001;
		for (auto pr : prob) {
			if (min > abs(an - pr))
				min = abs(an - pr);
			//cout << an << " " << min << " " << mins << endl;
		}
		if (min > mins) {
			mins = min;
			ans = an;
		}
	}

	cout << ans << '\n';
	return 0;
}