[Python] 백준 #6588- 골드바흐의 추측 [try_again]

문제

---

6588번: 골드바흐의 추측

코드

---

My answer(시간초과)

 

First Try

import sys
from itertools import combinations
res=[]

while(1):
    n=int(sys.stdin.readline())
    if(n==0):break
    tmp=[i for i in range(3,n+1) if i%2!=0]
    for i in range(len(tmp)):
        if(tmp[i]!=0):
            for j in range(i+1,len(tmp)):
                if(tmp[j]!=0 and tmp[j]%tmp[i]==0):
                    tmp[j]=0
    for i in combinations(tmp,2):
        if(sum(i)==n):
            res.append([i[0],i[1],abs(i[0]-i[1])])
    if(res!=[]):
        res=sorted(res, key=lambda x:-x[2])
        print("%d = %d + %d"%(n,res[0][0],res[0][1]))
    else:
        print("Goldbach's conjecture is wrong.")
    res=[]

Second Try

import sys

while(1):
    res,tmp2=[],[]
    n=int(sys.stdin.readline())
    if(n==0):break
    tmp=[1]*n
    for i in range(2,len(tmp)):
        if(tmp[i]!=0):
            for j in range(i+i,len(tmp),i):
                tmp[j]=0
            tmp2.append(i)
    tmp2.remove(2)
    tmp=tmp2
    for i in tmp:
        if((n-i) in tmp):
            res.append(i)
            res.append(n-i)
            break
    if(res!=[]):
        print("%d = %d + %d"%(n,res[0],res[1]))
    else:
        print("Goldbach's conjecture is wrong.")

Another answer

import sys

check = [0, 0] + [1] * 1000000
for i in range(2, 1001):
    if check[i] == True:
        for j in range(i + i, 1000001, i):
            check[j] = False
while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    A = 0
    B = n
    for _ in range(1000000):
        if check[A] and check[B]:
            print(f"{n} = {A} + {B}")
            break
        A += 1
        B -= 1
    else:
        print("Goldbach's conjecture is wrong.")

 

풀이

---

요즘 너무 스트레스 받는다. 문제자체는 그냥 푸는데 시간초과, 메모리초과 등등 때문에 못푸니까 시간이 무한정으로 걸린다. 그냥 문제를 못푸는거면 몇시간 끙끙 앓다보면 풀리는데 저런건 해결할 수가 없다. 결국 이번문제도 못풀어서 정답을 검색했다. 우선 큰틀은 동일했다. 우선 내 맨 처음 코드는 무식하게 풀었었다. 홀수집합을 구하고, 그 중 소수를 구하고, 그 조합들 중에 조건을 만족하는 놈들을 구하고, 차가 큰 순서대로 정렬해서 진짜 문제그대로를 풀었는데, 시간초과가 떠서 생각해보니 우선 조합을 할필요가 없이 경우의수를 제일 작은것부터 시작하면 여러개를 구한다음 정렬할 필요없이 맨처음 한개를 구하면 더이상은 구할 필요가 없다는 것을 알아냈다. 그래서 한개가 구해지면 그대로 정렬해서 코드가 엄청나게 단축됐음에도 코드는 안돌아갔다. 대충 뒤져보니 우선 소수를 구할 때 에라토스테네스의 체를 사용했는데, 이걸 테스트 케이스마다 반복하다 보니까 테스트케이스가 많아질수록 동일한 연산을 n번씩해서 오래걸렸고 또 마지막에 in을 사용했었는데 in또한 전체를 돌기 때문에 오래걸렸다. 그래서 생각한 방법이 에라토스테네스의 체는 주어진 범위 의 최대 10000001까지 한번만 구해놓고 쓰자는거였고, in을 대체할 방법은 찾지못했었다. 근데 이건 좀 이상한게 문제 설명에 소수로 만들지못하면 저 문자열을 출력하라고 되어있는데, 그래서 in을 사용해서 있으면 하고 없으면 출력하게 한건데, 골드바흐의 추측은 지금까지 모두 맞다고 증명돼서 무조건 소수로 만들 수 있다는 가정하에 코드를 작성해야 풀리는 것 같다. 그래서 in을 안쓰고 그냥 i면 n-i를 추가한다. 알고리즘을 공부해야되는 이유를 계속 느끼는데 너무 어렵다..