[파이썬] 9020 골드바흐의 추측

 

사실 좀 미루고 미뤘던 문제이다

 

문제 자체는 쉬운데 어떻게 뽑아낼지가 약간 고민인 문제였다

 

오늘 한 번 풀어보자라는 생각으로 시도했는데 그 결과들은 처참했다..

 

 

 

사실 4개는 같은 코드이다

 

뭔가 잘못 적혔나..? 하면서 바꾸다 보니 저리 나왔는데..

 

여하튼 문제점은 하나다

 

일단 문제가 된 코드를 보자

 

import sys input = sys.stdin.readline ary = [False]*10001 for i in range(2, 10001):     cnt =0     for p in range(2, int(i**0.5)+1):         if i%p ==0:             cnt=1     if cnt ==0:         ary[i]=True num = int(input()) cnt == False for i in range(int(num)):     cnt = False     tmp = int(input())     if ary[tmp//2]== True:         print (tmp//2, tmp//2)     else:         for p in range(tmp):             cnt == False             for k in range(p):                 if p+k==tmp and ary[p]==True and ary[k]== True:                     print(min(p,k), max(p, k))                     cnt = True             if cnt == True:                 break

 

일단 소수를 10001의 숫자만큼 돌려서 소수면 배열 칸에 True를 준다

 

그리고 입력되는 숫자만큼 for문을 돌려 짝을 찾아 출력한다

 

물론 저 코드는 지금 봐도 끔찍한 효율성이다 

 

그래도 답은 잘 나왔었다

 

혹시나 해서 이걸로 pypy로도 넣어봤는데 역시 실패했다

 

..

 

결국 저 부분의 효율을 높여야 하는데 머리를 싸맸다

 

결국 안 나와서 저 부분만 다들 어떻게 풀었나 봤는데 

 

정말 머리를 탁 칠 수밖에 없었다

 

로직은 그냥 반을 쪼갠 채로 비교를 시작하는 것이다

 

예를 들어서 3/5로 들어가는 8의 경우

 

4/4로 시작한다

 

for문을 4부터 시작 => 1까지

if문으로 들어온 값-for값과 for값이 모두 다 True == 4와 4는 True

 

이면 출력을 하고 아니면 넘어간다 

 

그럼 자연스레 for는 3일 때 3과 5, 답이 나오면 출력

 

이런 식이다 

 

그럼 당연히 5/5로 쪼개지는 10은 초장부터 그냥 쪼개졌으니 출력될 것이고

 

아니더라도 각각의 소수가 출력될 것이다

 

import sys input = sys.stdin.readline ary = [False]*10001 for i in range(2, 10001):     cnt =0     for p in range(2, int(i**0.5)+1):         if i%p ==0:             cnt=1     if cnt ==0:         ary[i]=True num = int(input()) for i in range(num):     a = int(input())     b= a//2     for p in range(b, 1, -1):         if ary[a-p] == True and ary[p]==True:             print(p, a-p)             break

 

항상 아침에 비몽사몽 하면서 풀어서 그런가 왜 저런 생각을 못 하는지 잘 모르겠다

 

여하튼.. 하나 더 풀었으니 패스패스