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

Problem

https://www.acmicpc.net/problem/9020

Solution

오답코드1 (시간초과)

import sys

# 소수 탐색
def prime_list(n):
    sieve = [True] * n
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False

    return [i for i in range(2, n) if sieve[i] == True]

# 골드바흐 파티션 구하기
def solve(n):
    j = 0
    arr = {} # 모든 파티션을 저장할 딕셔너리
    sosu = prime_list(n)
    while sosu[j] <= (n//2): # 소수가 n/2 이하인 경우
        if n-sosu[j] in sosu:
            arr[sosu[j]] = n-sosu[j]
        j += 1

    min = n
    x, y = 0, 0
    for k, v in arr.items(): # 차이가 최소인 파티션 찾기
        if abs(k - v) < min:
            min = abs(k - v)
            x, y = k, v
    return x, y

t = int(input())
for i in range(t):
    n = int(sys.stdin.readline())
    x,y = solve(n)
    print(x,y)

n 미만의 소수 중에서 합이 n이 나오는 모든 쌍을 찾아 딕셔너리에 저장 후 차이가 최소인 파티션을 리턴해 출력하는 코드이다.

오답코드2 (시간초과)

import sys

# 소수 탐색
def prime_list(n):
    sieve = [True] * n
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False

    return [i for i in range(2, n) if sieve[i] == True]

# 골드바흐 파티션 구하기
def solve(n):
    j = 0
    sosu = prime_list(n)
    while sosu[j] <= (n//2): # 소수가 n/2 이하인 경우
        if n-sosu[j] in sosu:
            x, y = sosu[j], n-sosu[j]
        j += 1

    return x, y

t = int(input())
for i in range(t):
    n = int(sys.stdin.readline())
    x,y = solve(n)
    print(x,y)

1번 코드에서 마지막으로 구한 파티션은 결국 차이가 최소인 파티션이기 때문에(n/2 이하인 소수만 찾았으므로) 따로 딕셔너리에 저장해서 비교하지 않고 바로 리턴했다.

정답코드

import sys

# 소수 탐색
def prime_list(n):
    sieve = [True] * n
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False

    return [i for i in range(2, n) if sieve[i] == True]

# 골드바흐 파티션 구하기
def solve(n):
    sosu = prime_list(n)
    j = len(sosu)-1
    while sosu[j]> n//2: # 소수가 n/2 초과인 경우
        j-=1
    while 1:
        if n-sosu[j] in sosu:
            x, y = sosu[j], n-sosu[j]
            break
        j -= 1
    return x, y

t = int(input())
for i in range(t):
    n = int(sys.stdin.readline())
    x,y = solve(n)
    print(x,y)

위의 2번과 같은 방식의 코드이지만 이번에는 소수를 중간부터 찾아서 내려오는 방식으로 짰다. 어쨌든 차이가 최소가 되려면 (x, y)값에서 x가 제일 큰 경우를 찾아야 하기 때문에 큰 값부터 찾는게 효율적이기 때문이다.

Ref.

https://www.acmicpc.net/board/view/82570