[문제풀이] Python- 백준 9020문제 (골드바흐의 추측)

www.acmicpc.net/problem/9020

(TMI - 너무 고통스러웠던 문제였다)

 

 

수학자 골드바흐가 제시한 추측한 유명한 미해결 문제로,

 

모든 짝수는 두 소수의 합으로 만들어 질 수 있다는 내용이다.

 

수 많은 시행착오.. (런타임 에러, 시간초과 등등)을 거쳐 해결한 방식은 아래와 같다.

[풀이 방식]

1.  Size = 10000의 배열을 만든 뒤, 각 숫자가 소수인 경우와 아닌 경우를 True / False로 입력하여 구별

(소수는 에라토스테네스의 체를 활용하여 구한다)

 

2. 출력 될 2개의 수는 오름차순이므로, 앞자리 수가 작아야하며, 주어진 값의 절반 값에서 부터 시작하며 배열을 이용하여 점점 작은 소수를 탐색한다. (ex 10,000이라면 5,000 이하의 소수)

 

3. 주어진 값에서 탐색되는 소수를 뺀뒤 나온 값이 소수인지를 판별한다.

 

4. 첫 번째로 도출 된 두 값이 가장 차이가 적으므로, 해당 값을 출력한다.

 

생각보다 시간초과로 너무 많이 고생해서 힘들었지만, 대부분의 알고리즘 문제들은 짧고 간결한 답을 가지고 있다는 것을 다시 한번 상기하면서 다른 문제들도 접근해야겠다.