사용자 도구

사이트 도구


ps:problems:boj:17103

골드바흐 파티션

ps
링크https://www.acmicpc.net/problem/17103
출처BOJ
문제 번호17103
문제명골드바흐 파티션
레벨실버 2
분류

소수 목록

시간복잡도O(nloglogn + tn/logn)
인풋사이즈n<=1,000,000, t<=100
사용한 언어Python
제출기록43480KB / 848ms
최고기록512ms
해결날짜2021/02/14

풀이

  • 먼저 1,000,000 이하의 소수 목록을 미리 구해서 set에 저장해 둔다.
  • 그러면, 각각의 N에 대해서 합이 N이 되는 소수 쌍의 갯수를 찾는 것은, 모든 소수 Pi를 순회하면서 N-Pi가 소수 목록에 포함되는지를 체크해서 그 갯수를 세면 된다.
  • 이렇게 구해진 소수 쌍의 갯수에는 순서만 다른 소수쌍도 포함되므로 이것을 보정하기 위해서 결과값을 2로 나눠서 출력해야 한다. 이때, 같은 소수가 두번 더해져서 얻어진 경우가 포함된 경우를 또 따로 고려해줘야 한다. 같은 소수를 두번 더해서도 N이 만들어질 수 있다면, 그 경우에는 카운트가 홀수로 나올 것이다. 그리고 출력할 값은 (카운트 - 1)/2 + 1 = 카운트/2 + 0.5가 되므로, 결국 그냥 모든 경우에 대해서 카운트/2 를 반올림한 값을 출력하면 된다.
    • 반올림을 할 때 python의 round로는 의도한 결과가 안나온다. sum(divmod(count,2))로 처리했다.
  • 소수 목록을 구하는 데에 O(nloglogn), 각각의 쿼리마다 모든 소수를 한번씩 순회해야 하고, 소수의 갯수는 O(n/logn)이니까, t개의 쿼리를 처리하는 것은 O(tn/logn). 합치면 O(nloglogn + tn/logn)

코드

"""Solution code for "BOJ 17103. 골드바흐 파티션".

- Problem link: https://www.acmicpc.net/problem/17103
- Solution link: http://www.teferi.net/ps/problems/boj/17103
"""

from teflib import numtheory


def main():
    T = int(input())
    N = [int(input()) for _ in range(T)]
    primes = set(numtheory.prime_list(max(N)))
    for n_i in N:
        count = sum(1 for p in primes if n_i - p in primes)
        print(sum(divmod(count, 2)))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
O S T U᠎ N
 
ps/problems/boj/17103.txt · 마지막으로 수정됨: 2021/02/14 12:05 저자 teferi