[백준-9020]골드바흐의 추측(C++)

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

9020번: 골드바흐의 추측

모든 짝수는 두 소수의 합으로 표현할 수 있다는 것이 골드바흐의 추측입니다.

짝수가 주어졌을 때 합으로 표현할 수 있는 두 소수를 찾으면 됩니다.

(여러개일 경우 차이가 가장 적은 두 소수를 찾으면 됩니다)

 

예)

8 = 3+5

10 = 5+5

16 = 5+11

 

이전에 포스팅한 소수찾기 문제를 응용하면 풀 수 있는 문제입니다.

 

문제 해결한 알고리즘

주어진 짝수를 n이라 하겠습니다.

(1/2)n+(1/2)n = n 입니다.(당연)

이 때 합하면 n이 되는 두 수가 동시에 (1/2)n보다 크거나 작을 수 없습니다.

동시에 크면 n보다 커져버리고 동시에 작으면 n보다 작은수만 만들 수 있기 때문이죠!

 

예)합하면 16이 되는 두 소수 찾기

16의 1/2는 8입니다.

그럼 8에 양쪽에 있는 두 소수를 찾습니다.

(만약 1/2한게 소수라면 그게 바로 정답이 됩니다.)

8근처에는 7과 11이 있습니다.

하지만 7+11은 18이기 때문에 더 작아져야하죠? 

이때는 11을 줄이는게 아니라 더 작은수를 줄입니다.

(이유는 위에서 말한 1/2+1/2 = 1 때문입니다)

7보다 작은 소수는 5

5+11을 하면 16이됩니다.

즉, 두 소수는 각각 (1/2)n보다 작은 소수+(1/2)n보다 큰소수가 된다는 것을 이해하셨다면 다 된겁니다!

 

소스코드(C++)

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

using namespace std;

int main() {
	int N;//테스트케이스
	vector <int> v; //입력 값
	vector <int> prime; //소수 배열
	vector <pair<int,int>> ans; //출력 값(소수 개수)
	int num = 0; //기준값 - 주어진 짝수의 반
	int a = 0; //기준값보다 작은 소수
	int b = 0; //기준값보다 큰 소수
	bool isPrime = true; //소수판별

	cin >> N; //테스트케이스 입력

	for (int i = 0; i < N; i++) { //입력
		int a, b;
		cin >> a;
		v.push_back(a);
	}

	prime.push_back(2); //소수 배열에 2추가 하고 시작

	//입력받은 최댓값까지의 소수 배열 만들기
	for (int i = 3; i <= *max_element(v.begin(), v.end()); i++) { //입력 값의 마지막 원소(최댓값)까지 반복
		isPrime = true;
		for (int j = 0; j < prime.size(); j++) { //소수 배열 크기 만큼 반복

			if (i >= prime[j] && i % prime[j] == 0) { //소수 배열 수보다 크면서 나누어 떨어지면 소수 아님
				isPrime = false;
				break;
			}
		}
		if (isPrime == true) { //위쪽 if문을 모두 통과 시 소수임
			prime.push_back(i); //소수 배열에 추가
		}
	}

	//두 소수 찾기
	for (int i = 0; i < v.size(); i++) {
		num = v[i] / 2; //기준값
		for (int j = 0; j < prime.size(); j++) {
			if (num >= prime[j]) { //기준값보다 작은 소수 찾기
				a = j;
			}
			if (num <= prime[j]) { //기준값보다 큰 소수 찾기
				b = j;
				break;
			}
		}
        
        //두 소수의 합이 주어진 수가 될 때까지 a, b 값 조정
		while (a >= 0 && a < prime.size() && b >= 0 && b < prime.size()) {
			if (prime[a] + prime[b] == v[i]) {//답 찾았을 때
				ans.push_back(make_pair(prime[a], prime[b]));
				break;
			}
			else if (prime[a] + prime[b] >= v[i]) {//주어진 수보다 크면 작은 값을 줄임
				a -= 1;
			}
			else if (prime[a] + prime[b] <= v[i]) { //주어진 수보다 작으면 큰값을 늘림
				b += 1;
			}
		}
	}
    
	for (int i = 0; i < ans.size(); i++) { //답 출력
		cout << ans[i].first <<' '<< ans[i].second << endl;; 
	}
}

 

소수 배열 만드는 부분은 소수찾기 포스팅을 참고하시면 됩니다!

 

1. 기준값(주어진 수의 반)지정
2. 기준값보다 한단계 작은 소수, 큰 소수 찾기
3. 두 소수의 합이 주어진 수라면 답
4. 두 소수의 합이 주어진 수보다 크면 작은 소수를 한단계 줄이기
5. 두 소수의 합이 주어진 수보다 작으면 큰 소수를 한단계 늘리기
6. 답 찾을 때까지 3-5단계 반복

https://suyeoniii.tistory.com/3

[백준-1978]소수 찾기(C++)