[백준] 17103번 문제 (골드바흐 파티션) 파이썬(Python) 풀이

def is_prime(num):
    if num == 1 or num == 0:
        return False
    else:
        for i in range(2, int(num ** 0.5)+1):
            if num % i == 0:
                return False
        return True


primes = [is_prime(i) for i in range(1000001)]
t = int(input())

for _ in range(t):
    n = int(input())
    left, right = 0, n
    count = 0

    while left <= right:

        while not primes[left]:
            left += 1
        while not primes[right]:
            right -= 1

        sum_num = left + right

        if sum_num == n:
            count += 1
            right -= 1
        elif sum_num > n:
            right -= 1
        else:
            left += 1

    print(count)

우선 최대 입력인 1,000,000 까지 for문을 돌면서 소수면 True 아니면 False의 형태로 primes 리스트에 할당 해줬다.

그리고 left, right 두 개의 포인터를 두어서 left + right가 입력된 숫자 n과 같으면 카운트를 해주면서 문제를 풀었다.

 

처음에는 Python3 컴파일러로 문제를 제출했는데, 시간 초과가 나서..

혹시나 하는 마음에 PyPy3 컴파일러로 문제를 제출했더니 문제가 풀려서 그냥 이대로 마무리 했다 ^_^

 

시간 제한이 0.5초라 좀 더 획기적인 방법으로 풀어야 될 것이라고 생각했으나,

일단 필자가 생각난대로 문제를 풀어 보았고, 그 방법의 풀이로 통과되서 기분이 좋았던 문제였다.