study gomi

[백준/baekjoon] 17103번 골드바흐 파티션 (파이썬) 본문

Practice/Baekjoon

[백준/baekjoon] 17103번 골드바흐 파티션 (파이썬)

공부하곰 2024. 1. 11. 03:41
728x90
반응형

내 제출

- 숫자의 범위가 정해져 있어서 에라토스테네스의 체를 써서 전체 소수를 먼저 구해뒀다.

(에라토스테네스의 체 설명 참고 : https://taetaegom.tistory.com/39)

- 골드바흐의 체 함수 내에서 잘 못 짠 게 있어서 계속 수정을 했다.

- 검사해야 하는 수는 그대로 두고 그 수의 절반 값 까지만 소수 -> 빼도 소수인지 확인하면 되는데 첨에 아무 생각 없이 비교 대상이 되는 소수 리스트 목록을 반으로 자르고 1~검사해야 하는 수를 비교했다. 오잉또잉...ㅋ

- 그 다음에는 바보같이 break를 달아서 검사중인 숫자가 소수가 아니면 그냥 바로 과정이 끝나버리게 했다.

- 여튼... 다시 보니 어려울 게 없는 건데 엄청 헤맸다.

def sieve_of_eratosthenes(num):
    primes = [True for _ in range(num + 1)]
    p = 2
    while p * p <= num:
        if primes[p]:
            for i in range(p * p, num + 1, p):
                primes[i] = False
        p += 1
    # 1은 소수 아니니까 2부터 마지막 숫자까지 num 까지
    return [p for p in range(2, num + 1) if primes[p]]


def goldbach_partition_count(check_n, primes):
    count = 0
    # ex 36
    # 2+34, 3+ 33, 4+ 32, ..., 18 + 18 => 18까지만 확인해 보면 됨.
    for check_prime in range(2, check_n // 2 + 1):
        # 소수가 아니면 그냥 패스
        if not primes[check_prime]:
            continue
        # 소수인데 원래 숫자에서 뺀 값도 소수인지 확인
        if primes[check_n - check_prime]:
            count += 1
    return count


# 1,000,000 이하의 소수 전부 찾기
max_num = 1000000
all_primes = sieve_of_eratosthenes(max_num)

# 소수 여부를 빠르게 확인하기 위한 리스트
is_prime = [False] * (max_num + 1)
for prime in all_primes:
    is_prime[prime] = True

# 테스트 케이스 개수
t = int(input())
for _ in range(t):
    n = int(input())
    print(goldbach_partition_count(n, is_prime))

 

결과

- 무려 세 번 틀리고 맞았다.

 

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

728x90
반응형