글 읽기 - [python] 계속 50%에서 시간초과가 뜹니다 ㅠㅠ

ss7ssy 2년 전 1

먼저 에라토스테네스의 체로 소수를 구하고, a와 b를 하나씩 증가 및 감소 시켜가면서 소수리스트에 있으면 출력하는 방식으로 진행했습니다..

예제에 대한 입출력은 잘 나오는데 백준에서 돌리면 계속 50%에서 시간초과가 뜹니다. ㅠ 어디에서 시간을 많이 잡아먹는지 모르겠습니다

어디가 문제인걸까요??? ㅜㅜ

import sys
input = sys.stdin.readline
print = sys.stdout.write

def prime_list(N: int) -> list:
  for i in range(3, N+1):
    if sieve[i] == True:
      for j in range(i+i, N+1, i):
        sieve[j] = False

while True:
  N = int(input())
  if N == 0:
    break
  sieve = [True]*1000001
  prime_list(N)

  a = 3; b = N-3
  for _ in range(N):
    if sieve[a]==True and sieve[b]==True:
      print(f"{N} = {a} + {b}\n")
      break
    else:
      a += 1
      b -= 1
  else:
    print( "Goldbach's conjecture is wrong.\n" )

rafle 2년 전 3

몇 가지만 말씀드릴게요.

1. sieve를 정의하고 prime_list를 체크하는 것은 while문 실행 전에 한 번만 하면 됩니다.

10만번의 테스트 케이스 동안 하나하나 소수를 구하면 시간 초과가 나겠죠.

prime_list(1000000)으로 딱 한 번만 구해놓고, 그 표를 계속 계산하시면 됩니다.

2. 마지막에 else가 if도 없는데 왜 쓰이는건가요?

참고로 Goldbach의 추측은 현재 알려진 모든 숫자에 대해 참이므로 이 부분은 없어도 됩니다.

3. for문이 얼마나 돌아야할지 되게 애매하네요. 저는 for문을 while (a <= b): 로 고쳤습니다. 등호는 N=6 때문에 있어야합니다.

ss7ssy 2년 전 0

해결했습니다!! 일일히 소수를 구하는 과정을 한번만 실행하도록 바꾸니 바로 진행되었습니다.

게다가 쓸모없는 부분까지 찝어주셔서 감사해요... 아직 배울게 많네요 감사합니다-!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[python] 계속 50%에서 시간초과가 뜹니다 ㅠㅠ

ss7ssy 2년 전 1

rafle 2년 전 3

ss7ssy 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말