백준 17103번 풀이

문제

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

17103번: 골드바흐 파티션

주어진 짝수의 골드바흐 파티션 개수 출력하기(인데 함정맛...)

 

Reference

https://ps.dabyeol.com/solutions/boj/17103/python

Problem Solving

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

글 읽기 - 파이썬) 시간 초과 관련 질문 (골드바흐 파티션)

https://wikidocs.net/21638#google_vignette

2. 소수 구하기 - 에라토스테네스의 체

 

풀이

9020번 이후로 오래간만에 돌아온 골드바흐 추측이다. 참고로 골드바흐 추측은 '2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다.'이고 9020번과 달리 이번에는 골드바흐 파티션이 몇개인지를 뽑아야 한다. (9020번 문제는 차가 제일 작은거 하나 뽑았음)

 

import sys

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

def isprime(a):
    sqrt = int(a ** 0.5)
    if a == 1: 
        return False
    for i in range(2,sqrt+1):
        if a % i == 0:
            return False
    else: 
        return True

prime = []
for i in range(1,10001):
    if isprime(i):
        prime.append(i)

for i in range(T):
    N = int(sys.stdin.readline())
    goldbach_count = 0
    goldbach_endpoint = N // 2
    for j in range(1,goldbach_endpoint+1):
        if j in prime and N - j in prime:
            goldbach_count += 1
    print(goldbach_count)

어? 9020번 코드 수정해서 내도 돼요?

 

아뇨 시간초과가 반기니까 내지 마십쇼. 내가 냈다가 시간초과 세번먹음.

 

뜬금포로 시간초과가 뜨길래 이게 뭐여 했는데, 위에 함수 정의해둔 걸 빼고 아예 에라토스테네스의 체 배열로 만들어야 한단다. 그니까 저것도 로직은 맞는데 일일이 계산해야 해서 시간을 잡아먹는다.

 

import sys

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

a = [False, False] + [True] * (T - 1)
primes = []

for i in range(2,T+1):
    if a[i]:
        primes.append(i)
        for j in range(2*i,T+1,i):
            a[j] = False

print(primes)

이게 에라토스테네스의 체인데 문제가 하나 있다. 얘가 맞아요 맞는데 문제 풀 때 이걸로 하면 인덱싱 잘못되니까 이걸로는 하지 말자. 이것도 내가 시행착오 겪어보고 알려주는거니까 새겨들으십시오. 22 입력했는데 숫자 이상해서 출력해보니까 합계 88떴어...

 

import sys

isprime = [True] * 1000001
isprime[0:2] = [False, False]
for i in range(2, 1001):
    if isprime[i]:
        for j in range(i * 2, len(isprime), i):
            isprime[j] = False

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

for i in range(T):
    N = int(input())

    count = 0
    for i in range(2, N // 2 + 1):
        if isprime[i] and isprime[N - i]:
            count += 1

    print(count)

찢었다 4트째에 해냄...

 

일단 내가 위에서 로직 맞는데 인덱싱 망한다고 쓰지 말라고 한 거랑 차이점이 뭐냐면 위 코드는 소수여야 리스트에 넣는다. 그니까 11번째가 11이라는 보장이 없음. 반면 아래 코드는 합성수여도 False로 들어가 있어서 11번째가 11이 된다. 그니까 위쪽 리스트는 소수'만' 있는 리스트라 인덱싱 망하는 것.