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

문제 설명

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

9020번: 골드바흐의 추측

 

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

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

해당 문제는, 입력받은 2보다 큰 짝수에 대하여 2개의 소수 합으로 나타내어 출력해야 하는 문제이다.

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

해당 알고리즘이 어색하다면, 아래의 링크도 함께 참고해보길 바란다.

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

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

이렇게 소수를 구하는 과정만 잘 해낸다면 크게 어렵지 않게 해결할 수 있는 문제로 보인다.

다만, 2개의 소수를 추려낼 때는 되도록 효율적인 접근을 할 수 있도록 노력해보았는데, 이에 대한 것은 아래에 적어놓았다.

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

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

 

코드의 실행 순서

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

 

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

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

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

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

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

 

3) 테스트 케이스의 수(n)를 입력받는다.

 

4) n의 크기만큼 반복문을 수행하여 아래의 연산을 수행한다.

- 임의의 합계(a)를 입력받는다.

- 2개의 소수를 추려냈는지에 대한 여부를 나타낼 변수 cnt를 0으로 초기화하여 선언한다.

- 2중 반복문을 통하여 a에 대한 2개의 소수를 탐색해본다.

이때, 하나의 제어 변수(j)는 a/2부터 시작하여 점차 감소하게끔 하고, 다른 제어 변수(k)는 a/2부터 시작하여 점차 증가하게끔 하였다. (효율적인 연산을 위해 중앙값에서부터 탐색을 시작하였다.)

탐색하는 중, j와 k가 모두 소수이며 j+k가 a라면 이를 크기 순대로 적절히 출력해준 뒤 탐색을 멈춘다.

(이때, 탐색을 완전 종료할 수 있도록 cnt에 1을 더하고 이에 따라 완전 종료되도록 if문을 추가로 구성해준다.)

- 출력을 완료하였다면 다음 테스트 케이스를 수행하도록 한다.

 

5) 모든 테스트 케이스들을 수행하였다면, 실행 종료한다.

반응형

 

성공한 코드

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

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

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

	int n, a;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;

		int cnt = 0;
		for (int j = a / 2; j >= 0; j--) {
			for (int k = a/2; k <= a; k++) {
				if (j + k == a && arr[j] == 0 && arr[k] == 0) {
					cout << j << " " << k << endl;
					cnt++;	break;
				}
			}
			if (cnt != 0) { break; }
		}
	}
}

 

제출 결과

(2022.07.10 백준 9020번 문제 제출 결과)