[python] 백준 6588 - 골드바흐의 추측

출처 : 백준, https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

 

의외로 시간초과가 안 떠서 놀랐던 문제

당연히 시간초과 뜰 줄 알았는데

 

 

첫 번째 풀이 : 실패

 

def Goldbach(n, prime_set):
  a, b = n//2, n//2

  for i in range(0, a):
    if a in prime_set and b in prime_set:
      print('%d = %d + %d' % (n, a, b))
      return

    a -= 1
    b += 1
      
if __name__ == '__main__':
  num_arr = []

  while True:
    n = int(input())
    if n == 0:
      break

    num_arr.append(n)

  max_val = max(num_arr)

  prime_set = set(i for i in range(2, max_val+1))

  for i in range(2, int(max_val**0.5) + 1):
    prime_set -= set(j for j in range(2*i, max_val + 1, i))

  for num in num_arr:
    Goldbach(num, prime_set)

 

만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다라는 조건을 못 본 상태에서

가운데부터 시작해서 a는 1씩 줄이고, b는 1씩 늘려서 계산하는 방법

 

 

두 번째 풀이 : 실패

 

def Goldbach(n, prime_set):
  for a in range(2, n//2):
    b = n - a
    if a in prime_set and b in prime_set:
      print('%d = %d + %d' % (n, a, b))
      return
      
if __name__ == '__main__':
  num_arr = []

  while True:
    n = int(input())
    if n == 0:
      break

    num_arr.append(n)

  max_val = max(num_arr)

  prime_set = set(i for i in range(2, max_val+1))

  for i in range(2, int(max_val**0.5) + 1):
    prime_set -= set(j for j in range(2*i, max_val + 1, i))

  for num in num_arr:
    Goldbach(num, prime_set)

 

b-a가 가장 클 때 이므로 가장 작은 수부터 찾아가는 방법

홀수인데 2를 넣어서 실패함.

 

 

세 번째 풀이 : 실패

 

def Goldbach(n, prime_set):
  for a in range(3, n//2):
    b = n - a
    if a in prime_set and b in prime_set:
      print('%d = %d + %d' % (n, a, b))
      return
      
if __name__ == '__main__':
  num_arr = []

  while True:
    n = int(input())
    if n == 0:
      break

    num_arr.append(n)

  max_val = max(num_arr)

  prime_set = set(i for i in range(2, max_val+1))

  for i in range(2, int(max_val**0.5) + 1):
    prime_set -= set(j for j in range(2*i, max_val + 1, i))

  for num in num_arr:
    Goldbach(num, prime_set)

반례

6
0

#  6 = 3 + 3

 

n//2가 홀수이면서 소수일 수 있다는 점을 간과하지 못해 틀림.

 

 

네 번째 풀이 : 성공

 

def Goldbach(n, prime_set):
  for a in range(3, n//2 + 1):
    b = n - a
    if a in prime_set and b in prime_set:
      print('%d = %d + %d' % (n, a, b))
      return
      
if __name__ == '__main__':
  num_arr = []

  while True:
    n = int(input())
    if n == 0:
      break

    num_arr.append(n)

  max_val = max(num_arr)

  prime_set = set(i for i in range(2, max_val+1))

  for i in range(2, int(max_val**0.5) + 1):
    prime_set -= set(j for j in range(2*i, max_val + 1, i))

  for num in num_arr:
    Goldbach(num, prime_set)

 

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

문제를 잘 읽자. 틀렸을 때 range 범위 안에 있는 수가 답이 될 수 있는지 고려하자.