백준) 골드바흐 파티션

문제 ) 골드바흐 파티션

 

해당 문제에서 요구하는 사항은 짝수 숫자 N을 주어 졌을 때 N 보다 작은 소수의 두 합이 N이 되는 가짓수를 출력해 달라는 것이다. 이때 3 + 5, 5 + 3은 하나로 취급 한다.

 

문제 지문 자체는 어렵지 않으나 이제 어떤 식으로 해서 가짓수를 출력해야 될지가 문제였었다.

차근차근 고민은 및 손으로 규칙이 없나 찾아보다가

6 = 1

8 = 1

10 = 2

12 = 1

이라는 테스트 케이스를 보고 곰곰히 생각을 해보았다

6 = 3 + 3, (2 + 4, 2는 소수이지만 4는 소수가 아니다)

8 = 5 + 3, (2 + 6, 2는 소수이지만 6은 소수가 아니다)

10 = 7 + 3, 5 + 5, ( 2 + 8, 2는 소수이지만 8은 소수가 아니다)

12 = 7 + 5 , (11 + 1, 1은 소수가 아니므로 탈락)

 

해당 식을 적어보니 확실히 규칙이 보였다. 구하고자하는 N - sosu = min_sosu 가 되면 된다

만약 N - sosu != min_sosu이면 카운트를 안하면 된다.

 

이렇게 일단 숫자의 가짓수를 체크에 대한 규칙을 찾았고 이제 소수를 구하기만 하면 이문제는 해결이 될걸로 생각이 된다.

 

이 때까지 소수를 구하는 문제를 많이 풀기도하여 쉽게 생각을 하고 소수를 구하는 식을 작성한 뒤 문제를 풀었는데 어찌된 영문이지 시간 초과를 하게 되었다.

 

이떄까지 내가 주로 사용한 소수 구한 코드

dp = [0] * 1000001
dp[2] = 1
for i in range(2, 1000001):
    is_ok = True
    for j in range(2, int(i ** 0.5) + 1):
        if i % j == 0:
            is_ok = False
            break
    if is_ok:
        dp[i] = 1

 

전체 코드

import sys
dp = [0] * 1000001
dp[2] = 1
for i in range(2, 1000001):
    is_ok = True
    for j in range(2, int(i ** 0.5) + 1):
        if i % j == 0:
            is_ok = False
            break
    if is_ok:
        dp[i] = 1

T = int(sys.stdin.readline().strip())
for _ in range(T):
    N = int(sys.stdin.readline().strip())
    count = 0
    visited = {}
    for idx in range(N):
        if dp[idx] == 0: continue
        if dp[N - idx] == 1 and N - idx >= idx:
            count += 1

    sys.stdout.write(f'{count}\n')

 

소수구하는 식을 제외하고는 시간초가 날만한 부분이 전혀 보이지 않았다.

그렇다면 소수를 구하는 방법이 너무 오래 걸린다는 건데 이를 현재의 나로써는 생각하기 어려워 어쩔 수 없이 구글링을 통하여 좀더 빠른 소수구하는 방식을 손에 넣을 수 있었다.

 

향상된 소수 공식 코드

p = [1] * 1000001
sosu_list = []
for i in range(2, 1000001):
    if dp[i] == 1:
        sosu_list.append(i)
        for j in range(i*2, 1000001, i):
            dp[j] = 0

 

의 소수를 구하는 부분은 일단 전체 값을 일정한 값으로 통일을 한 뒤 통일한 값으로 된 자리이면 소수이고 이후 소수의 배수는 전부 다른 값으로 대체하여 중복 검사를 최대한 피하는 방식이다

 

찾은 방식으로 기존 코드의 소수 구하는 부분에 적용을 한 뒤 제출을 하니 무사히 코드가 통과됨을 확인하였다.

 

전체 코드

import sys
dp = [1] * 1000001
sosu_list = []
for i in range(2, 1000001):
    if dp[i] == 1:
        sosu_list.append(i)
        for j in range(i*2, 1000001, i):
            dp[j] = 0

T = int(sys.stdin.readline().strip())
for _ in range(T):
    N = int(sys.stdin.readline().strip())
    count = 0
    visited = {}
    for sosu in sosu_list:
        if sosu > N: break
        if dp[N - sosu] == 1 and N - sosu >= sosu:
            count += 1

    sys.stdout.write(f'{count}\n')

 

다음에는 구글링 없이도 내가 코드를 짤 수 있게 해당 문제는 나의 오답노트 링크로 남겨 놓고 추후 시간이 지나면 다시 풀어봐야 할거 같다