[백준] 9020 : 골드바흐의 추측

문제

시간초과 시

특히 소수문제 같은 경우엔 제한이 4 ≤ n ≤ 10,000 이런 식으로 걸려 있다면 수를 입력할 때마다 소수를 구할 필요가 없다.
먼저 리스트의 크기를 할당해놓는 것이 중요하다.
그리고 그 리스트에 (중요한 건 0부터 시작해서 나아가야 한다는 것) 소수이면 True, 소수가 아니면 False를 준다.

시간초과 풀이

import sys

def sol(n):
    nlist = [] # 각각의 수 이하의 소수 모음
    
    for i in range(2, n):
        for j in range(2, int(i**0.5)+1):
            if i % j == 0:
                break
        else:
            nlist.append(i)
    alist = [] # 소수의 합이 n이 되는 것
    for i in range(len(nlist)):
        for j in range(i, len(nlist)):
            if nlist[i] + nlist[j] == n:
                alist.append([nlist[i], nlist[j]])
    flist = []       
    for i in range(len(alist)):
        flist.append(alist[i][1] - alist[i][0])
    
    a1 = alist[flist.index(min(flist))][0]
    a2 = alist[flist.index(min(flist))][1]
    answer = str(a1) + " " + str(a2)
    return answer


t = int(sys.stdin.readline())

for i in range(t):
    n = int(sys.stdin.readline())
    print(sol(n))
    

참고 풀이 이해

참고 풀이

import sys
from itertools import combinations_with_replacement


nlist = [False,False] + [True]* 10002 # 먼저 만들어두기

for i in range(2, 10001):
    for j in range(2, int(i**0.5)+1):
        if i % j == 0:
            nlist[i] = False
            break
    else:
        nlist[i] = True

def sol(n, nlist): # 참고 블로그 https://deokkk9.tistory.com/20
    a = n//2 # 두 수의 차가 적은 수를 구하는 것이므로 입력받은 n의 중간부터 비교해 나감
    b = a
    while a > 0:
        print(nlist[a], nlist[b])
        if nlist[a] and nlist[b]:
            print(a,b)
            break
        else:
            a -= 1
            b += 1


t = int(sys.stdin.readline())

for i in range(t):
    n = int(sys.stdin.readline())
    sol(n, nlist)

참고 풀이 2

def isSosu(n):
    if n == 1 :
        return False
    elif n == 2:
        return True
    elif n % 2 == 0 :
        return False
    else :
        for j in range(3, n, 2):
            if n % j == 0:
                return False
        else :
            return True
    return False
T = int(input())
for i in range(T):
    c = int(input())
    half = c//2 # 두 수 간의 차이가 적도록 c//2부터 시작!
    while True:
        # 1) half가 소수인가?
        if isSosu(half):
            # 2) c - half가 소수인가?
            left = c-half
            if isSosu(left):
                print(f'{half} {left}')
                break
            # 2-1) 아니면 half -1 
            else :
                half-=1
        else :
            # 1-1) 아니면 half -1
            half-=1

혼자 푼 풀이

import sys

t = int(sys.stdin.readline().strip())
nlist = [int(sys.stdin.readline()) for i in range(t)]
slist = [False, False] + [True] * 10002 # slist[i]가 i를 가리키게 하도록 0부터 값 부여

# 10000까지 소수 리스트 생성
for i in range(2, 10001):
    if i == 1:
        continue
    
    for j in range(2, int(i**0.5)+1):
        if i % j == 0: 
            slist[i] = False # 소수가 아니기 때문에 False
            break
    else:
        slist[i] = True # 소수이므로 True
        
def check(n):
    f = n//2
    s = f
    while f > 0: # 이렇게 조건 주는 게 좋음!
        if slist[f] and slist[s]:
            print(str(f) + " " + str(s))
            break
        else:
            f -= 1
            s += 1

for i in nlist:
    check(i)