[소수] 6588. 골드바흐의 추측

1. 문제 해결 전략

시간초과가 걸려서 결국 해결하지 못했다. 에라토스테네스의 체 구현은 문제가 없었지만, while문 부분에서 정답을 찾아놓고도 반복문을 계속 돌려 시간초과가 났다. 결과를 구하기 위해서 더해지는 두 수를 찾을 때, 여러 경우가 나오는 것을 대비해서 모든 경우를 vector에 넣은 후 두 수의 차가 최대가 되는 해를 찾으려 했는데.. 이것이 문제였다.

 

일단 그런 과정 필요 없이 두 수의 차이가 최대가 되려면 어떻게 해야할지를 먼저 생각해보면 입력 받은 수보다 작은 소수들 중 가장 큰 소수와 가장 작은 소수의 합이 입력 받은 수가 되면 되는 것.

나는 left,right로 이를 표현했는데.. 결국 left + right = n이기 때문에 left는 가장 작은 소수부터 right은 가장 큰 소수부터 내려오면서 두 값이 소수인지만 확인되면 둘이 더해 n이 되는 수중 가장 큰 값이 먼저 발견되는 것이다..

 

나는 이것을 몰라서.. 수가 구해졌음에도 입력 개수만큼 반복을 돌리다 보니 시간 초과가 난 것이다.

 

#include <iostream>
#include <vector>
using namespace std;
bool av[1000001];
int main()
{
	av[0] = true;
	av[1] = true;
	for (int i = 2; i*i < 1000001; i++)
	{
		if (av[i] == false)
		{
			for (int j = i * i; j < 1000001; j += i)
			{
				av[j] = true;
			}
		}
	}

	av[2] = true;

	int k = 0;
	while (true)
	{
		scanf("%d", &k);
		if (k <= 4)
			break;
		bool key = false;
		int right = 0;
		for (int i = 3; i < k; i++)
		{
			right = k - i;
			if ( av[i] == false && av[right] == false)
			{
				printf("%d = %d + %d\n", i + right, i, right);
				key = true;
				break;
			}
		}
		if (key == false)
			puts("Goldbach's conjecture is wrong.\n");
	}

	return 0;
}

 

 

2. 걸린 시간

실패

 

3. 느낀점

처음에 cin,cout 문제인가 싶어서 printf, scanf로 바꾸었는데도 안됐다.. 조건을 만족하는 경우는 하나 뿐이란 것을 알아체지 못한 것. 이것은 순수 실력 부족이라 할 말이 없다.

 

4. 링크

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