문제

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

---

풀이

시간초과

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

bool isPrimeNumber(int x){ 
	if(x < 2) return false; 
	
	for(int i = 2; i * i <= x; i++){
		if(x % i == 0) return false; 
	} 
	
	return true;
}

void findPartition(vector<int> v, int n){
	pair<int, int> pii; 

	int minValue = 1e9; 
	for(int i = 0; i < v.size(); i++){
		for(int j = 0; j < v.size(); j++){
			int sum = v[i] + v[j];
			if(sum == n){
				int gap = abs(v[i] - v[j]);
				
				if(gap == 0){ // 동일한 숫자 (최소 차이)
					cout << v[i] << " " << v[j] << "\n"; 
					return; 
				}
				
				if(gap < minValue){
					minValue = gap;
					pii.first = min(v[i], v[j]); 
					pii.second = max(v[i], v[j]); 
				}
			}
		}
	}

	cout << pii.first << " " << pii.second << "\n"; 
}

int main()
{	
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	// n 이하의 소수들을 모두 구한다. 
	// 더해서 n이 되는 두개의 소수를 구한다. 

	int t; 
	cin >> t; 
	
	while(t--){
		int n; 
		cin >> n; 

		vector<int> v; 
		for(int i = 2; i <= n; i++){ 
			if(isPrimeNumber(i)) { 
				// 작은 수부터 먼저 삽입 
				v.push_back(i); 
			}
		}

		findPartition(v, n);
	}

    return 0;
}

• 2 이상 n 이하의 소수를 찾는데, O($n * \sqrt{n}$)의 시간복잡도
• 더해서 n이 되면서 크기 차이가 가장 작은 두 소수를 구하는데, O($m^2$)의 시간복잡도
• n은 최대 10,000

답안

https://codesyun.tistory.com/67

#include <iostream>
using namespace std; 

bool isPrime(int x){
	if(x < 2) return false; 

	for(int i = 2; i * i <= x; i++){
		if(x % i == 0) return false; 
	}

	return true; 
}

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

	int t; 
	cin >> t; 
	
	while(t--){
		int n; 
		cin >> n;

		for(int i = n / 2; i >= 2; i--){
			if(isPrime(i) && isPrime(n - i)){
				cout << i << " " << n - i << "\n"; 
				break; 
			}
		}
	}

    return 0;
}

i를 n/2부터 2까지 줄여나가면서, i와 n-i 모두 소수가 되는 조합을 구한다.

• n/2부터 시작해야 i와 n-i의 차이가 최소이다.
• i와 n-i의 합은 n이라는 것을 이용한다.