[BaeKJoon] 6588번: 골드바흐의 추측 문제 풀이 (Python)

1일 최소 1문제 풀기! 1일차 오늘은 백준 홈페이지에 있는 골드바흐의 추측 문제를 풀어보았습니다.

6588번: 골드바흐의 추측

 

골드바흐의 추측 문제는 

 

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

 

라는 추측을 백만이하의 모든 짝수에 대해서 검증하는 문제입니다.

 

이것을 검증하면서 입력한 숫자를 만들 수 있는 두 홀수 소수의 조합 중 두 수의 차가 가장 큰 조합을 찾아서

 

C = A + B 의 형식으로 출력을 해주면 됩니다.

 

처음 문제를 보고 떠오른 아이디어는

 

먼저 입력 받은 수보다 작은 소수를 모두 구하고 가장 큰 소수와 가장 작은 소수와 더한 값이

 

입력받은 값이 나올때 그 두개의 값을 가지고 출력값을 만드는 것을 생각해보았습니다.

 

먼저 N 이하의 모든 소수를 구하는 함수를 만들고

def getPrimaryNums(N):
    a = [2, 3, 5]
    for i in range(6, N):
        if i % 2 != 0 and i % 3 != 0 and i % 5 != 0:
            a.append(i)
    return a

각각 입력받은 값에 대해서 가장 큰 값과 가장 작은 값을 더해보며 값이 나올경우

출력 후 break_flag를 True로 변경하여 반복문을 중단하였습니다.

 

만약 반복문이 종료가 되었는데도 원하는 조건의 값이 없을때 break_flag가 False일 경우

Goldbach의 추측은 틀렸다라고 출력해주도록 하였습니다.

while(True):
    N = int(input())
    
    if N == 0:
        break

    primary_nums = getPrimaryNums(N)

    primary_nums_len = len(primary_nums)

    break_flag = False

    for i in primary_nums[::-1]:
        if break_flag == True:
            break
        for j in range(len(primary_nums)):
            if N == (i + primary_nums[j]):
                print("{} = {} + {}".format(N, primary_nums[j], i))
                break_flag=True
                
    if break_flag == False:
        print("Goldbach's conjecture is wrong.")

 

한번 이 코드를 제출해 보았습니다.

시간초과로 통과를 하지 못하였습니다.

 

생각해보니 GoldBach의 추측이 틀렸을 경우 이중 반복문이 끝까지 실행되어

O(N²)의 시간복잡도를 가지게 됩니다.

 

어떻게 시간복잡도를 줄여볼까 고민해보다가 리스트 내의 숫자로 모든 조합을 만들어 주는 combination라이브러리가 생각났습니다.

 

두번째 아이디어는

입력받은 N 이하의 모든 소수를 구하고

 

combination 라이브러리를 활용하여 N이하의 소수 두 개로 만들 수 있는 조합을 만들고

 

그 조합중에서 두 수의 합이 N인 것을 찾은 뒤

 

두 수의 차가 가장 큰 조합을 찾아 출력까지 해주는 방법을 생각해 보았습니다.

 

from itertools import combinations

while(True):
    N = int(input())
    if N == 0:
        break
    primary_nums = getPrimaryNums(N)

    combs = list(combinations(primary_nums, 2))

    new_combs = []

    for comb in combs:
        if sum(comb) == N:
            new_combs.append(comb)

    sub = []

    for comb in new_combs:
        sub.append(comb[1] - comb[0])

    max_sub = max(sub)

    for i in range(len(new_combs)):
        if max_sub == sub[i]:
            print("{} = {} + {}".format(N, new_combs[i][0], new_combs[i][1]))

결과가 나오기는 하나 테스트에서 1,000,000을 입력하게 되면...

너무 많은 조합을 만들게되어 메모리를 많이 점유하는 문제가 발생했습니다.

역시나 시간초과!

 

결과는 나오나 계속 시간 초과의 문제가 발생하여 다른 방법은 없을지 검색해보니

 

에라토스테네스의 체의 방법을 쓰면 해결할 수 있다고하여 먼저 에라토스테네스의 체의 방법 문제를 풀어보았습니다.

 

[BaeKJoon] 2960번: 에라토스테네스의 체 문제 풀이 (Python)

먼저 에라토스테네스의 체의 개념과 문제를 풀고왔으니 이제 골드바흐의 추측 문제에 적용해보겠습니다.

def getPrimaryNum_Eratos(N):
    nums = [True] * (N + 1)
    for i in range(2, len(nums) // 2 + 1):
        if nums[i] == True:
            for j in range(i+i, N, i):
                nums[j] = False
    return [i for i in range(2, N) if nums[i] == True]

while(True):
    N = int(input())
    
    if N == 0:
        break

    primary_nums = getPrimaryNum_Eratos(N)

    primary_nums_len = len(primary_nums)

    break_flag = False

    for i in primary_nums[::-1]:
        if break_flag == True:
            break
        for j in range(len(primary_nums)):
            if N == (i + primary_nums[j]):
                print("{} = {} + {}".format(N, primary_nums[j], i))
                break_flag=True
                
    if break_flag == False:
        print("Goldbach's conjecture is wrong.")

소수를 구하는 법이 문제가아닌 뒤 쪽에 문제가 있는 것 같습니다.

 

이번에는 조금 다르게 접근하여 보기로 했습니다.

 

N 이하의 소수를 모두 찾고 가장 작은 소수부터 소수의 개수만큼 반복문을 돌면서 N - 소수 를 했을때

 

그 값도 소수인 경우 print를 해주면 될 것이라고 생각했습니다.

def getPrimaryNum_Eratos(N):
    nums = [True] * (N + 1)
    for i in range(2, len(nums) // 2 + 1):
        if nums[i] == True:
            for j in range(i+i, N, i):
                nums[j] = False
    return [[i for i in range(2, N) if nums[i] == True], nums]


while(True):
    N = int(input())
    
    if N == 0:
        break
    primary_nums = getPrimaryNum_Eratos(N)[0]
    primary_bools = getPrimaryNum_Eratos(N)[1]
    
    for i in range(len(primary_nums) // 2):
        if primary_bools[N-primary_nums[i]] == True:
            print("{} = {} + {}".format(N, primary_nums[i], N-primary_nums[i]))
            break

하지만 결과는 처참했습니다.

이제 어디서 더 줄일 수 있을까?

고민해보니 이 문제는 반복문을 돌면서 0이 나올때까지 계속 값을 구해야합니다.

근데 지금의 방식은 while 반복문이 실행될때마다 새로 소수를 구하고있습니다.

 

애초에 1,00,000 이하의 모든 소수를 구해두고 하면 어떨까? 생각해보았습니다.

def getPrimaryNum_Eratos(N):
    nums = [True] * (N + 1)
    for i in range(2, len(nums) // 2 + 1):
        if nums[i] == True:
            for j in range(i+i, N, i):
                nums[j] = False
    return [[i for i in range(2, N) if nums[i] == True], nums]

primary_nums = getPrimaryNum_Eratos(1000000)[0]
primary_bools = getPrimaryNum_Eratos(1000000)[1]
while(True):
    N = int(input())
    
    if N == 0:
        break

    
    for i in range(N // 2):
        if primary_bools[N-primary_nums[i]] == True:
            print("{} = {} + {}".format(N, primary_nums[i], N-primary_nums[i]))
            break

과연 결과는!!!!!

드디어.....

9번의 시도 끝에 성공하였습니다.

 

계속 풀다보면 다른 문제는 더 쉽게 풀 수 있을거라 생각하며 매일 1문제씩은 꼭 풀어보려합니다.

 

읽어주셔서 감사합니다.

 

SOMJANG/CODINGTEST_PRACTICE