[C++][Baekjoon][Math] 6588번 골드바흐의 추측(feat. C++ 입출력 시간 단축)

[문제]

6588번: 골드바흐의 추측

"4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다." 는 골드바흐의 추측이 맞는지 틀렸는지 확인하는 문제.

 

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 

만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다.

두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

 

[풀이]

시간 제한 1초.

테스트 케이스의 개수는 100,000개.

확인해야할 짝수 정수 n의 범위. 6 ≤ n ≤ 1000000

 

1초의 제한 시간을 넘기지 않으려면 연산 횟수가 1억 번을 초과하면 안된다.

 

테스트 케이스의 개수가 100,000개이고 확인해야할 짝수 정수의 범위가 1,000,000 까지이므로 1부터 n까지 모든 수를 확인한다면 최악의 경우 100,000 * 1,000,000 의 연산을 수행하게 되어 100,000,000,000 = 1,000억 번의 연산을 수행해야 한다. 이 때의 연산 처리 시간은 1000초가 될 것이다. 루트n까지 확인한다고 해도 100,000 * 1,000 = 100,000,000 = 10억 번의 연산을 수행해야 한다. 아직 10초...

 

따라서 에레토스테네스의 체를 활용하여 문제를 풀어야 함을 알 수 있다. 에레토스테네스의 체는 2부터 자신의 배수를 다 지우는 방법으로 시간복잡도 O(N(log(logN)))를 가진다. 

 

그러나.......... 아무리 줄여도 입출력시간을 줄이지 못해 시간초과가 났다. 그리고 1번, 2번 풀이 모두 아래 구문을 추가해주니 해결되었다. 이 구문을 안쓰고 해결하려면 cin, cout 대신에 scanf, prinf를 사용하면 해결가능하다. (4번 코드 참고. 이미 C언어를 사용했다면 상관없음!)

cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);

 

마치면서... C++ 입출력 시간 단축에 관하여 정리해보자면!

 

1. cin, cout 대신에 scanf, printf를 쓰자. scanf는 0.798초의 수행시간을 가지는데, cin은 2.051초의 시간을 갖는다고 한다.(출처: https://2heedu.tistory.com/64)

참고로 위의 구문으로 c++과 c의 표준 스트림의 동기화 끄면 입출력 속도를 줄일 수 있다. 하지만 c와 c++ 입출력 순서가 보장되지 않아 두 문법을 섞어썼을 때, 순서가 뒤섞여 나올 수 있고, c++ 스트림들의 thread 안정성 역시 보장되지 않는다.

2. endl 대신 "\n"를 쓰자. endl은 개행을 할 뿐 아니라 내부 버퍼도 비워주므로 "\n"보다 속도가 느리다.

 

[코드] 3, 4번 코드가 정답 코드!

 

1번 풀이. 시간초과.

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

bool canGoldBahGuess(int num);
bool isPrime(int num);

int main() {
    int num;
    while(true) {
        cin >> num;
        if (num == 0) break;
        if (!canGoldBahGuess(num)) cout << "Goldbach's conjecture is wrong.\n";
    }
    return 0;
}

bool canGoldBahGuess(int num) {
    for (int i = 3; i <= num/2; i++) {//3부터 홀수&소수 판별
        if (i % 2 != 0 && isPrime(i) && (num-i) % 2 != 0 && isPrime(num - i)){
            cout << num << " = " << i << " + " << num - i << "\n";
            return true;
        }
    }
    return false;
}

bool isPrime(int num) {
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) return false;
    }
    return true;
}

 

2번 풀이. 시간초과

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

void MakeDecimalTable();
bool canGoldbach(int num);

const int MAX_SIZE = 1000000;
int decimalTable[MAX_SIZE + 1];

int main() {
    int num;
    bool answer = true;

    MakeDecimalTable();

    while(true) {
        cin >> num;
        if (num == 0) break;
        if (!canGoldbach(num)) cout << "Goldbach's conjecture is wrong.\n";
    }
    return 0;
}

void MakeDecimalTable() {
    fill_n(decimalTable, sizeof(decimalTable)/sizeof(int), 1);
    for (int i = 2; i <= sqrt(MAX_SIZE ); i++) {//2부터 소수판별하러 gogo
        if (decimalTable[i] != 0) {
            for (int j = 2; i*j <= MAX_SIZE ; j++) {//그 배수를 모두 0으로 바꿈
                decimalTable[i*j] = 0;
            }
        }
    }
}

bool canGoldbach(int num) {
    for (int i = 3; i <= num / 2; i++) {//3부터 소수 판별
        if (decimalTable[i] && decimalTable[num - i]) {
            cout << num << " = " << i << " + " << num - i << "\n";
            return true;
        }
    }
    return false;
}

 

3번 풀이. 통과.

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

void MakePrimeTable();
bool canGoldbach(int num);

const int MAX_SIZE = 1000000;
int primeTable[MAX_SIZE + 1];

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    int num;
    bool answer = true;

    MakePrimeTable();

    while(true) {
        cin >> num;
        if (num == 0) break;
        if (!canGoldbach(num)) cout << "Goldbach's conjecture is wrong.\n";
    }
    return 0;
}

void MakePrimeTable() {//에라토스테네스의 체
    for (int i = 2; i <= sqrt(MAX_SIZE); i++) {//2부터 소수판별하러 gogo
        if (primeTable[i] == 0) {
            for (int j = 2; i*j <= MAX_SIZE; j++) {//그 배수를 모두 0으로 바꿈
                primeTable[i*j] = 1;
            }
        }
    }
}

bool canGoldbach(int num) {
    for (int i = 3; i <= num / 2; i++) {//3부터 소수 판별
        if (primeTable[i] == 0 && primeTable[num - i] == 0) {
            cout << num << " = " << i << " + " << num - i << "\n";
            return true;
        }
    }
    return false;
}

 

4번 풀이. 통과

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

const int MAX_SIZE = 1000000;

int main() {
	vector<int> primeTable;
	bool primeNoCheckTable[MAX_SIZE + 1];
	for (int i = 2; i*i <= MAX_SIZE; i++) {//2부터 소수판별하러 gogo
		if (!primeNoCheckTable[i]) {
			if(i != 2) primeTable.push_back(i);
			for (int j = i + i; j <= MAX_SIZE; j += i) {//그 배수를 모두 소수 확인을 끝냈다는 의미로 true로 바꿈
				primeNoCheckTable[j] = true;
			}
		}
	}

	int num;
	bool answer;
	while (true) {
		scanf("%d", &num);
		if (num == 0) break;
		for (int prime : primeTable) {
			if (!primeNoCheckTable[num - prime]) {
				printf("%d = %d + %d\n", num, prime, num - prime);
				answer = true;
				break;
			}
		}
		if (!answer) printf("Goldbach's conjecture is wrong.\n");
	}
	return 0;
}