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

문제 설명

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

6588번: 골드바흐의 추측

 

접근 방법 - 에라토스테네스의 체 알고리즘을 응용한 소수 연산 문제

백준의 6588번 문제는 에라토스테네스의 체 알고리즘을 이용하여 구한 소수를 통해 연산해야 하는 문제이다.

해당 문제는, 각 케이스마다 주어지는 2보다 큰 짝수에 대하여 2개의 소수 합으로 나타내어 출력해야 하는 문제이다.

에라토스테네스의 체 알고리즘에 대한 설명은 이전 ps글에서도 다룬 적이 이미 있기 때문에 이 링크를 아래에 기재해놓았다.

또한, 이 문제와 유형은 똑같지만 난이도는 비교적 낮은 문제에 대한 풀이도 이전에 ps글에서 다루었기 때문에 이것도 함께 기재하였다.

해당 알고리즘이 어색하다면, 아래의 링크들을 한번 참고해보길 바란다.

https://smary-it.tistory.com/157

[백준 BOJ] 2960번 에라토스테네스의 체 (C++/cpp)

https://smary-it.tistory.com/231

[백준 BOJ] 9020번 골드바흐의 추측 (C++/cpp)

여기서, 답이 여러 개인 경우엔 정답인 두 숫자의 차이가 가장 큰 것을 출력하라고 하니 이 점도 함께 참고해야 할 것이다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 에라토스테네스의 체 알고리즘을 수행하기 위한 배열(arr)을 전역 변수로 선언해둔다.

 

2) 에라토스테네스의 체 알고리즘을 수행한다. (연산 방법을 알고 있다면 이 설명은 넘어가도 좋다.)

(이때, arr의 배열값이 0이라면 소수임을 뜻하며 1이라면 소수가 아님을 뜻한다고 가정한다.)

- 우선, 0과 1은 소수가 아니기 때문에 각 arr의 배열값을 1로 설정해둔다.

- 2부터 시작하여 자기 자신을 제외한 배수들을 인덱스로 갖는 배열값들은 모두 1로 설정해둔다.

자기 자신을 제외한 모든 소수의 배수들은 소수가 아니라는 점을 이용한 것이다.

 

3) 무한 반복문을 수행하여 아래의 연산을 취한다.

- 값(a)을 입력받는다. (여기서, 0을 입력받으면 해당 반복문을 종료한다.)

- 정답을 출력했는지에 대한 여부를 확인하기 위한 변수 cnt를 0으로 초기화하여 선언한다.

- 반복문을 통해 정답을 탐색한다. (필자 같은 경우에는, 시간 초과를 피하기 위해 반복문 하나로 정답을 탐색하였다.)

현재 탐색 중인 값(i)과 a/2에 대하여 대칭되는 값(a-i)이 둘 다 소수라면 이를 정답으로 출력한다.

(여기서, 이 반복문의 탐색법은 바깥쪽에서부터 a/2 중앙으로 폭을 좁혀오기 때문에, 이 반복문을 통하여 첫 번째로 발견된 정답이 두 숫자 간 격차가 가장 큰 경우이다. 따라서 즉시 정답으로 출력해야 한다.)

정답을 출력하였다면, cnt에 1을 더한 뒤 탐색을 멈추도록 한다.

- 만일 해당 케이스에 대한 정답이 출력되지 않았다면, cnt의 값도 그대로 0일 것이다. 따라서 이 경우엔 문제에 제시된 문자열을 출력하도록 한다.

 

4) 위 무한 반복문이 종료되었다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 6588번 코드
int arr[1000001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	arr[0] = 1;	arr[1] = 1;
	for (int i = 2; i < 500001; i++) {
		if (arr[i] == 1) { continue; }
		for (int j = 2; i * j < 1000001; j++) {
			arr[i * j] = 1;
		}
	}

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

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

 

제출 결과

(2022.07.11 백준 6588번 문제 제출 결과)