백준 17103번(silver 2) : 골드바흐 파티션 (소수의 합으로 이루어진 수)

 

17103번: 골드바흐 파티션

---

 

 내가 작성한 코드 - 시간초과 

import sys
import math

input = sys.stdin.readline

# 소수 판명
def is_primeNum(n):
    if n == 1:
        return False
    for i in range(2, math.trunc(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

primeNum_list = []
for i in range(2, 500001):
    if is_primeNum(i):
        primeNum_list.append(i)

t = int(input())
lst = [int(input()) for _ in range(t)]

for i in range(t):
    cnt = 0
    num = lst[i]
    for j in range(2, (num//2)+1):
        if j in primeNum_list:
            if is_primeNum(num-j):
                cnt += 1
    print(cnt)

 

 

 풀이 참고하여 다시 작성한 코드 - 정답 (2668ms) 

import sys
import math

input = sys.stdin.readline

# 에라토스테네스의 체 알고리즘
array = [True for i in range(1000001)]

for i in range(2, int(math.sqrt(1000000))+1):
    if array[i] == True:
        j = 2
        while i*j <= 1000000:
            array[i*j] = False
            j += 1

t = int(input())
lst = [int(input()) for _ in range(t)]
for i in range(t):
    cnt = 0
    num = lst[i]
    for j in range(2, (num//2)+1):
        if array[j] and array[num-j]:
            cnt += 1
    print(cnt)

 

 

 수행시간을 줄이기위해 수정한 코드 (1096ms) 

import sys
input = sys.stdin.readline

primeNum = []
check = [0]*1000001
check[0] = 1
check[1] = 1

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

t = int(input())
for _ in range(t):
    cnt = 0
    n = int(input())
    for i in primeNum:
        if i >= n:
            break
        if check[n-i] == 0 and i <= n-i:
            cnt += 1
    print(cnt)

 

까다로워서 다른 사람들의 풀이를 많이 참고하였는데, 그래도 코드를 직관적으로 바로 이해하기 쉽지 않아서 따로 노트에 적으며 모두 이해하도록 공부하였다.

 

 마지막 코드 노트정리 

 

실버 4~5 까지는 무난하게 풀 수 있지만 아직 실버2 수준은 내겐 어렵다 ㅎㅎ;ㅠ