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

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

9020번: 골드바흐의 추측

---

문제

---

문제 풀이

나는 '두 소수의 차이가 가장 작은 것을 출력' 이라는 조건을 보고, 애초에 n을 2로 나누어 거기서부터 시작하면 어떨까? 하는 생각부터 시작했다.

 

그러다 예제를 보고 어차피 더하면 n이 나와야 하니 n / 2 + k와 n / 2 - k가 둘 다 소수인 k를 찾으면 정답이겠구나 싶어 코드를 설계하게 되었다. 발상이 빨리 되지 않았다면 어려운 문제였을 것 같다.

 

 

C++ 코드 전문

	#include <algorithm>
	#include <iostream>
	using namespace std;
	bool arr[10001];
	void isPrime() {
	int i = 2;
	arr[0] = false;
	arr[1] = false;
	while (i <= 10000) {
	if (arr[i])
	for (int j = i + i; j <= 10000; j += i)
	if (arr[j]) arr[j] = false;
	i++;
	}
	}
	// n / 2를 mid라고 했을 때, mid - k와 mid + k가 모두 소수인 것을 찾으면 된다.
	int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T;
	cin >> T;
	fill(arr, arr + 10000, true);
	isPrime();
	for (int i = 0; i < T; ++i) {
	int n;
	cin >> n;
	int mid = n / 2;
	for (int k = 0; k < mid; ++k) {
	if (arr[mid - k] && arr[mid + k]) {
	cout << mid - k << " " << mid + k << "\n";
	break;
	}
	}
	}
	return 0;
	}

view raw 9020_골드바흐의 추측 (22.04.08 성공).cpp hosted with ❤ by GitHub

 

Python 코드 전문

	arr = [False, False] + [True] * (10000 - 1)
	i = 2
	# 에라토스테네스의 체
	while i <= 10000:
	if arr[i]: # 지워나가는 과정
	for j in range(i + i, 10000 + 1, i):
	if arr[j]:
	arr[j] = False
	i += 1
	T = int(input())
	while T:
	n = int(input())
	mid = n // 2
	for k in range(mid):
	if (arr[mid - k] and arr[mid + k]):
	print(f"{mid - k} {mid + k}")
	break
	T -= 1

view raw 9020_골드바흐의 추측 (22.04.08 성공).py hosted with ❤ by GitHub

 

소감

발상이 된다면 빠르게 풀 수 있었을 문제다. 관건은 실전에서도 이런 아이디어가 나오냐는 것인데 잘 할 수 있을까 모르겠다.