백준 17103 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

골드바흐 파티션 문제이다.

 

시간초과 문제로 가장 많이 고생했던 문제라 생각된다.

 

결과적으로 다른 블로거의 글을 참고하여 풀 수 있었지만, 코드가 거의 일치한다..

 

코드부터 보자

 

코드

import sys as s

array = [1] * 1000002

array[:2] = 0, 0

prime = []

for i in range(2, 1000002):

    if array[i]:

        prime.append(i)

        for j in range(i*i, 1000002,i):

            array[j] = 0

           

n = int(s.stdin.readline())

for _ in range(n):

    count = 0

    m = int(s.stdin.readline())

    for k in prime:

        if k >= m:

            break

        if array[m-k] and k <= m-k:

            count += 1

   

    print(count)

 

출처 : https://greentea31.tistory.com/24

백준 17103 - 골드바흐 파티션 [파이썬]

아래 블로그 주인분의 코드와 98% 일치한다.

 

대단하신 분 같다..

 

문제를 풀며 코드를 쓰다가, 시간초과가 도저히 해결되지 않아 찾은 블로그인데 이미 그때부터 코드의 70 퍼가 일치했었다. ㅋㅋㅋ

 

나는 순서만 다른 같은 경우를 세지 않기위해, array2라는 리스트를 만들어 비교했었다.

 

해당 과정에서 당연히 시간을 더 사용했고, 다른부분에서 어떻게든 줄이기 위해 이런저런 시도를 많이 했다.

 

하지만 어떤 시도를 해도 요구치만큼 줄일 순 없었다.

 

그러다 array2를 사용하지 말고, 타 블로그 주인분의 코드를 분석해봤다.

 

k <= m-k 부분이다.

 

해당 부분에서 이해하는데 많은 시간을 썼다.

 

간단하게 요약하면 k와 m-k 중 k 가 더 작을 때만 반영하는 조건이다.

아 또한, 참고 블로그 주인분은 소수를 prime이라는 리스트에 넣고 불러와 사용하는 방식을 사용하였다.

 

그 방법이 더 좋을 것 같아 나도 채택하였다.