[백준] 17103번 골드바흐 파티션

💡문제접근

• 입력한 T개의 숫자 중에서 가장 최댓값을 구해 1부터 최댓값까지의 수 중에서 에라토스테네스의 체를 통해서 소수를 걸러내는 작업을 수행한다.
  매 테스트케이스마다 에라토스테네스의 체를 돌리는 것보다 최댓값만 찾아서 그 범위까지 에라토스테네스의 체를 한 번만 시행해주면 시간을 확연히 차이가 나게 된다.
• 마지막으로 해당 짝수가 두 개의 소수의 합으로 표현이 가능한 경우를 찾을 때 구하고자 하는 개수보다 2배씩 증가되어 나왔는데 범위를 끝까지 돌려서 두 소수의 순서가 서로 다른 것도 다르게 계산이 되었다. 이 부분에서 많이 헤맸다. 절반으로 나눈 범위만을 탐색해서 순서가 다른 것을 세지 않게끔 설정해주면 된다.

💡코드(메모리 : 38228KB, 시간 : 2604ms)

import sys
input = sys.stdin.readline

T = int(input().strip())
num = []
max_num = -1
for _ in range(T):
    N = int(input().strip())
    num.append(N)

max_num = max(num)
arr = [True] * (max_num+1)
arr[0] = False
arr[1] = False
for i in range(2, max_num+1):
    if arr[i]:
        for j in range(i*i, max_num+1, i):
            arr[j] = False

for i in num:
    cnt = 0
    for j in range((i//2) + 1):
        if arr[j] and arr[i-j]:
            cnt += 1
    print(cnt)

📌 시간 초과 코드(TLE)

• 시간 초과 발생 원인 : 매 테스트케이스마다 에라토스테네스의 체를 시행해줘서 그런 것...?

import sys
input = sys.stdin.readline

def add(li):
    return li[0] + li[1]

T = int(input().strip())
for _ in range(T):
    N = int(input().strip())
    arr = [True] * (int(1e6) + 1)
    arr[0] = False
    arr[1] = False
    for i in range(2, N+1):
        if arr:
            for j in range(i*i, N+1, i):
                arr[j] = False
    li = []
    for i in range(len(arr)):
        if arr[i]:
            li.append(i)

    half = N // 2
    cnt = 0
    for i in range(half):
        first = half - i
        second = half + i
        if first in li and second in li:
            cnt += 1
    print(cnt)

💡소요시간 : 47m