[백준 BOJ] 6588 : 골드바흐의 추측(C++)

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

6588번: 골드바흐의 추측

아이디어 흐름

1. 아이디어 구상

소수에 대한 문제가 크게 특정 범위 안의 소수를 알아야하는 경우, 해당 수가 소수인지 판별하는 경우 이렇게 두 가지가 있다고 생각하는데, 해당 문제는 1,000,000 까지의 소수를 알아야했으므로 에라토스테네스의 체를 이용하기로 했다.

또한 그렇게 소수를 판별하고, 소수만을 따로 모은 prime_arr 를 만들어서 int tmp = num - prime_arr[i] 에 대해 tmp가 prime_arr 배열에 있다면 정답을 출력해야겠다고 생각을 했다.

2. 초기 아이디어의 한계, 수정

시간복잡도도 고려 안하고서는 아이디어가 완벽하다고 생각하여 진짜 저렇게 코드를 냈다. 당연히 시간 초과가 나왔다. 1,000,000까지 에라토스테네스의 체로 소수 구하는 것만 10억 연산이고, 위 아이디어처럼 소수배열을 따로 만들어서 수를 찾아다니는 반복문도 굉장히 불필요한 과정인 시간복잡도에 대한 생각이 너무 없었다.

구한 소수를 다른 배열에 다시 저장한다거나 하는 등 불필요한 작업을 최대한 없애보았다. 에라토스테네스의 체로 소수를 구하는데 사용했던 배열을 그대로 사용하여 코드를 다시 작성하였다. 

그럼에도 시간초과가 나와 그 때는 구글링을 하였고, cin을 사용하고 싶으면

ios_base::sync_with_stdio(0);
cin.tie(0);

해당 코드로 동기화를 해주어야 코드가 통과된다는 글들이 있어서 위 코드를 추가한 후 정답을 받았다..

3. 코드

#include <iostream>
#include <cmath>
using namespace std;

bool arr[1000000];
void findPrime() {

	arr[0] = true;
	arr[1] = true;

	for (int i = 2; i < sqrt(1000000); i++) {
		if (arr[i]) continue;

		for (int j = i + i; j < 1000000; j += i) {
			arr[j] = true;
		}
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	findPrime();

	while (1) {
		int num;
		cin >> num;
		if (num == 0) break;

		for (int i = 3; i < 1000000; i += 2) {
			if (num - i <= 0) {
				cout << "Goldbach's conjecture is wrong." << '\n';
				break;
			}
			else if (!arr[i] && !(arr[num - i])) {
				cout << num << " = " << i << " + " << (num - i) << '\n';
				break;
			}
		}
	}
}

4. 아쉬운점

1. 항상 시간복잡도를 먼저 생각했는데, 이번에 정작 시간복잡도가 타이트한 문제에서 이걸 생각을 안했다. 항상 어떤 알고리즘을 사용할 것 같고, 시간복잡도는 어떻게 될지 먼저 생각해본 후 시간 제한 안에 들어오는지 생각해보자
2. 배열인덱싱에 자신이 없어서 소수판정에 사용한 arr 배열을 사용을 회피하고 소수배열을 다시 만들어서 이용하려고 했던 것 같다. 어려운 것도 아니고 [num - i] 만 생각했으면 되는건데, 배열 인덱스 다루는 것에 익숙해져야할 필요성을 크게 느꼈다.