[BOJ] 9020 - 골드바흐의 추측

문제

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

2보다 큰 짝수의 소수 곱(골드바흐 파티션)을 찾는 문제

난이도

난이도 中, 소요시간 20분 

풀이 과정

저번에 소수 문제를 풀어봤으니 이어서 소수 카테고리를 마저 풀기로 했다.

지난 번에 2581번에서 썼던 소수 구하는 알고리즘을 다음과 같이 조금 개선했다.

#include <iostream>
#include <vector>
bool isPrime(int n)
{
	if (n == 2)
		return true;
	if (n == 1 || n % 2 == 0)
		return false;
	
	for (int j = 3; j * j <= n; j+= 2)
	{
		if (n % j == 0)
			return false;
	}
	return true;
}

2가 아닌 짝수일 경우 절대 소수가 아니므로

반복문을 돌리기 전에 n이 2일 때는 true를 return하고, 짝수일 때는 false를 return하도록 바꿔주고 3에서부터 2씩 더해가면서 n을 나눠봄으로써 반복 횟수를 줄여봤다.

이제 2보다 큰 짝수가 주어지면 그 짝수의 소수 인수를 구해야 한다.

그런데 문제에서 n의 골드바흐 파티션이 여러 쌍인 경우 두 소인수의 차가 가장 작은 경우만 출력하라고 했으므로, n을 2로 나눈 지점부터 시작하고 찾으면 끝내는 식으로 코드를 짜는 것이 바람직할 것으로 생각했다.

n은 짝수이기 때문에 무조건 2로 나누어 떨어진다.

이 나눠진 두 조각을 left와 right라고 하자. 최초에는 left와 right가 동일하다.

만약 left가 2가 아닌 짝수인 경우 절대 소수일 수 없으므로

left에서는 1을 빼주고 right에서는 1을 더해준다.

(left가 2인 경우에는 4 = 2x2로, 파티션이 바로 끝난다.)

그럼 두 수는 홀수가 되고, 소수일 가능성이 생긴다.

이제 isPrime 함수를 거쳐 left와 right가 소수인지 확인하고, 둘 다 소수라면 가장 차가 적은 경우의 파티션을 찾았다.

둘 다 소수가 아닌 경우, left에서는 2를 빼고 right에서는 2를 더해가면서 다시 두 수가 소수인지를 검사한다. 두 수 모두 소수일 경우, 파티션을 찾았으니 반복문을 끝내면 된다.

이를 그대로 소스코드로 작성하면 다음과 같다.

파티션 과정을 진행하는 goldbachPartition 함수에서 소인수 2개를 return하기 위해 results라는 배열을 만들어 넣어주었다.

#include <iostream>
#include <vector>

using namespace std;

bool isPrime(int n)
{
	if (n == 2)
		return true;
	if (n == 1 || n % 2 == 0)
		return false;
	
	for (int j = 3; j * j <= n; j+= 2)
	{
		if (n % j == 0)
			return false;
	}
	return true;
}

vector<int> goldbachPartition(int n)
{
	int left, right;
	vector<int> results;	// 결과를 담은 배열
	results.resize(2);
	left = right = n / 2;
	if (left % 2 == 0 && left != 2)	// 2로 나눈 것이 2가 아닌 짝수일 경우 절대 소수가 될 수 없으므로
	{
		left -= 1;
		right += 1;
	}

	if (isPrime(left) && isPrime(right))	// 소수인지 확인해서 둘 다 소수이면 파티션 성공
	{
		results[0] = left;
		results[1] = right;
	}
	else
	{
		while (left >= 2)
		{
			left -= 2;
			right += 2;
			if (isPrime(left) && isPrime(right))	// 소수인지 확인해서 둘 다 소수이면 파티션 성공, 반복문 끝냄
			{
				results[0] = left;
				results[1] = right;
				break;
			}
		}
	}
	return results;
}

int main(void)
{
	int test = 0;
	cin >> test;
	
	for (int t = 0; t < test; t++)
	{
		int n = 0;
		cin >> n;
		vector<int> results;
		results = goldbachPartition(n);
		
		printf("%d %d\n", results[0], results[1]);
	}
	return 0;
}

좀 더 생각해보면 더 효율적으로 짤 수도 있을 것 같으나 귀찮으니 패쓰~~~