◎ 자료구조와 알고리즘/백준(BOJ) 문제풀이

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

reo91004 2022. 4. 8. 19:55
반응형

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

 

9020번: 골드바흐의 추측

1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아

www.acmicpc.net


문제


문제 풀이

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

 

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

 

 

C++ 코드 전문

 

Python 코드 전문

 

소감

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

반응형