백준 알고리즘 9020

#include

#include
#include
using namespace std;
bool arr[10001];
int minone(vector v,int n) {
	vector v1;
	int temp;
	for (int i = 0; i < v.size(); i++) {
		temp = (n - v[i]) - v[i];
		if (temp < 0)
			temp = temp * -1;
		v1.push_back(temp);
	}
	int mi = 10000, ind;
	for (int i = 0; i < v1.size(); i++) {
		if (mi > v1[i]) {
			mi = v1[i];
			ind = i;
		}
	}
	return v[ind];
}
int main() {
	memset(arr, 1, sizeof(arr));
	vector v;
	arr[1] = false;
	for (int i = 4; i <= 10000; i += 2) {
		arr[i] = false;
	}
	for (int i = 3; i <= 10000; i += 2) {
		if (arr[i]) {
			for (int k = i * 2; k <= 10000; k += i) {
				arr[k] = false;
			}
		}
	}
	int T;
	cin >> T;
	int n;
	int tmp;
	for (int i = 0; i < T; i++) {
		cin >> n;
		if (arr[n - 2]) {
			v.push_back(2);
		}
		for (int i = 3; i < n; i += 2) {
			if (arr[i] && arr[n-i]) {
				v.push_back(i);
			}
		}
		tmp = minone(v, n);

		cout << tmp << " " << n - tmp << "\n";

			v.clear();
	}
//	while (1);
	return 0;
}

골드바흐 파티션을 얻어내는 것 자체는

n에 소수를 빼줘서 나온 값이 소수면 골드바흐 파티션이다. 라는 쉬운 접근이 있어서 간단했으나

문제의 조건중에 '골드바흐 파티션이 복수일 경우 그 두 숫자의 차가 가장 적은 것을 출력한다.'

가 있기 때문에

vector 컨테이너를 활용한 minone()함수, 골드바흐 파티션중 가장 차가 적은 소수를 찾아내는 함수를 작성.

minone()함수는 인덱스에 따른 차를 모두 구한 뒤에 그중 가장 작은 값의 인덱스를 얻어내어 해당 소수를 리턴.

반환받은 소수와 n에서 해당 소수를 뺸 값을 공백으로 구분하여 출력.