(파이썬) 백준 17103번 골드바흐 파티션 풀이 python3

백준 17103 문제

풀이

def ari(a):

  c = [True for i in range(a+1)]

  for i in range(2,int((a**0.5)+1)):

    if c[i]:

      for j in range(i+i,a+1,i):

        c[j]=False

  return c

소수를 인덱스 값으로 찾을 수 있는 리스트를 형성한다.

0,1을 제외하고 소수는 모두 True값을 갖는다. 0과 1은 굳이 False로 바꾸지 않고 나중에 이후값부터 찾으면 된다.

a = int(input())

짝수로 주어진 개수를 입력받는다.

 

bs = [int(input()) for i in range(a)]

리스트로 주어진 짝수들을 다 집어 넣는다. 그 이유는 제일 큰 친구를 찾아서 그 친구로 소수찾기 함수를 만들어 놓으면, 시간절약이 되기 때문이다. 처음에 입력받을 때마다 만드니까 시간 초과가 났고, 미리 최대치 100만개를 만들어도 시간 초과가 났다.

 

b = max(bs)

c = ari(b)

리스트 bs에서 제일 큰 값을 b에 넣고 ari함수에 넣어준다.

 

for i in bs:

  cnt = 0

cnt에 파티션을 충족하면 +1할 것이다.

 

  for j in range(2,i//2+1):

여기서 range를 2부터 시작하고, 서로 위치만 바뀌는 것은 같은 것으로 본다고 했으므로, 반띵한다.

 

    if c[j] and c[i-j]:

      cnt+=1

 

  print(cnt)