[c++] 6588 백준 문제풀이(시간초과 해결)

1. 문제

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

6588번: 골드바흐의 추측

 

2. 시간초과 코드 

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

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

int main(){
	
	int n;
	int i,j;
	bool flag= true;
	while(1){
		cin >>n;
		if(n==0){
			break;
		}
		for( i=3;i<=n/2;i+=2){
			j= n-i;
			if(isPrime(i) && isPrime(j) && i+j==n){
				cout << n << " = " << i << " + " << j << "\n";
				flag = false;
				break;
			}
		}
		if(flag==true){
			cout << "Goldbach's conjecture is wrong." << "\n";	
		}		
	}

	return 0;
}

 

3. 해결방법

(1) 에라토스테네스의 체

: 2부터 n까지 수 중 소수 찾을 때 사용

• n+1 크기 갖는 bool 배열 저장 (이때, 나는 default값 false로 초기화 ⇒ 나는 그래서 헷갈릴 수 있기에 배열명을 isComposite로 해놓는다)
  → 새로 알게 된 것 : c++은 bool배열 초기화하지 않으면 default로 false로 초기화 / c언어는 default로 true로 초기화
  
  
• i=2부터 반복문 시작하여 2의 배수들을 모두 true로 변경 (0,1은 검사할 필요 x)
• 이때 i는 #include <cmath> 선언하고 sqrt함수 이용하여 sqrt(i)까지 돌린다
  → 소수를 판별할 때 sqrt(n)까지만 조사해도 해당 값이 소수인지 판별가능
• j=i*i부터 n까지 j+=i을 해주며 배열의 값이 false이면 true를 해준다 
• 배열을 다 완성하고 나면 배열값이 false인 것이 소수인 것이다

(2) 에라토스테네스의 체를 이용한 소스코드 (해결 x)

⇒ 보통 대부분 에라토스테네스의 체를 이용하면 해결이 가능하다. 하지만 내 소스코드는 이유가 무엇인지 모르겠으나 계속 시간초과가 떴다. 

#include <iostream>
#include <cmath>
#define MAX_SIZE 1000000
using namespace std;
bool isComposite[MAX_SIZE]; //어차피 주어지는 n은 짝수 정수니까 검사할 필요 x
bool flag = true;

int main() {
	for (int i = 2;i <= sqrt(MAX_SIZE);i++) {
		if (!isComposite[i]) {
			for (int j = i * i;j < MAX_SIZE;j += i) {
				isComposite[j] = true;
			}
		}

	}

	while (1) {
		int n;
		cin >> n;
		if (n == 0) {
			break;
		}
		for (int i=3;i <= n / 2;i += 2) {
			
			if (!isComposite[i] && !isComposite[n-i]) {
				cout << n << " = " << i << " + " << n-i << "\n";
				flag = false;
				break;
			}
		}
		if (flag) {
			cout << "Goldbach's conjecture is wrong";
		}
		flag = true;
	}
	return 0;
}

 

 

4. 시간초과 최종해결법

: 시간을 줄일 수 있는 방법을 서치하다가 찾아낸 방법

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

(1) ios_base::sync_with_stdio(false)

: C의 stdio와 C++의 iostream의 동기화를 비활성화시킴
: 기본적으로 C++와 C의 표준 스트림은 동기화가 되어있기에 C++에서 printf,scanf 사용이 가능하였다. 즉, C와 C++이 동일한 버퍼를 공유하고 있었는데 동기화를 끊으면 C++ 표준 스트림이 독립적으로 IO 버퍼링을 할 수 있어 성능을 높여 시간을 줄일 수 있다
※ 주의사항 : 동기화가 비활성된 경우 버퍼가 분리된 상태이기에 C의 scanf,gets,getchar,printf,puts,putchar과 같은 입출력함수를 혼용하면 안됨
 

(2) cin.tie(NULL), cout.tie(NULL) (NULL 대신 nullptr, 0도 가능)

: 원래 cout과 cin, 입출력은 묶여있기에 입력요청이 들어오면 출력 버퍼에 내용이 있는 경우 버퍼를 비워 출력하게 된다
: 입출력이 반복될 경우 일일이 버퍼를 지우느라 시간이 오래 걸린다
: 이때 입출력 묶음을 풀게 된다면 입출력 순서가 순차적으로 되지 않을 수 있다.
 
cf. endl
: endl의 내부동작을 보면 아래와 같다 
: 즉, 출력 버퍼를 비우는 작업을 수행하기에 시간이 오래 걸릴 수 있으므로 endl대신 '\n'을 사용하자

ostream & endl(ostream &ostm){
	ostm<<'\n';
    fflush(stdout);
    return ostm;
}

 

(3) 최종 소스코드

#include <iostream>
#include <cmath>
#define MAX_SIZE 1000000
using namespace std;
bool isComposite[MAX_SIZE];
bool flag = true;

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

	for (int i = 2;i <= sqrt(MAX_SIZE);i++) {
		if (!isComposite[i]) {
			for (int j = i * i;j < MAX_SIZE;j += i) {
				isComposite[j] = true;
			}
		}

	}

	while (1) {
		int n;
		cin >> n;
		if (n == 0) {
			break;
		}
		for (int i=3;i <= n / 2;i += 2) {
			
			if (!isComposite[i] && !isComposite[n-i]) {
				cout << n << " = " << i << " + " << n-i << "\n";
				flag = false;
				break;
			}
		}
		if (flag) {
			cout << "Goldbach's conjecture is wrong";
		}
		flag = true;
	}
	return 0;
}