[백준] 9020 : 골드바흐의 추측
문제
시간초과 시
특히 소수문제 같은 경우엔 제한이 4 ≤ n ≤ 10,000 이런 식으로 걸려 있다면 수를 입력할 때마다 소수를 구할 필요가 없다.
먼저 리스트의 크기를 할당해놓는 것이 중요하다.
그리고 그 리스트에 (중요한 건 0부터 시작해서 나아가야 한다는 것) 소수이면 True, 소수가 아니면 False를 준다.
시간초과 풀이
import sys
def sol(n):
nlist = [] # 각각의 수 이하의 소수 모음
for i in range(2, n):
for j in range(2, int(i**0.5)+1):
if i % j == 0:
break
else:
nlist.append(i)
alist = [] # 소수의 합이 n이 되는 것
for i in range(len(nlist)):
for j in range(i, len(nlist)):
if nlist[i] + nlist[j] == n:
alist.append([nlist[i], nlist[j]])
flist = []
for i in range(len(alist)):
flist.append(alist[i][1] - alist[i][0])
a1 = alist[flist.index(min(flist))][0]
a2 = alist[flist.index(min(flist))][1]
answer = str(a1) + " " + str(a2)
return answer
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
print(sol(n))
참고 풀이 이해
참고 풀이
import sys
from itertools import combinations_with_replacement
nlist = [False,False] + [True]* 10002 # 먼저 만들어두기
for i in range(2, 10001):
for j in range(2, int(i**0.5)+1):
if i % j == 0:
nlist[i] = False
break
else:
nlist[i] = True
def sol(n, nlist): # 참고 블로그 https://deokkk9.tistory.com/20
a = n//2 # 두 수의 차가 적은 수를 구하는 것이므로 입력받은 n의 중간부터 비교해 나감
b = a
while a > 0:
print(nlist[a], nlist[b])
if nlist[a] and nlist[b]:
print(a,b)
break
else:
a -= 1
b += 1
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
sol(n, nlist)
참고 풀이 2
def isSosu(n):
if n == 1 :
return False
elif n == 2:
return True
elif n % 2 == 0 :
return False
else :
for j in range(3, n, 2):
if n % j == 0:
return False
else :
return True
return False
T = int(input())
for i in range(T):
c = int(input())
half = c//2 # 두 수 간의 차이가 적도록 c//2부터 시작!
while True:
# 1) half가 소수인가?
if isSosu(half):
# 2) c - half가 소수인가?
left = c-half
if isSosu(left):
print(f'{half} {left}')
break
# 2-1) 아니면 half -1
else :
half-=1
else :
# 1-1) 아니면 half -1
half-=1
혼자 푼 풀이
import sys
t = int(sys.stdin.readline().strip())
nlist = [int(sys.stdin.readline()) for i in range(t)]
slist = [False, False] + [True] * 10002 # slist[i]가 i를 가리키게 하도록 0부터 값 부여
# 10000까지 소수 리스트 생성
for i in range(2, 10001):
if i == 1:
continue
for j in range(2, int(i**0.5)+1):
if i % j == 0:
slist[i] = False # 소수가 아니기 때문에 False
break
else:
slist[i] = True # 소수이므로 True
def check(n):
f = n//2
s = f
while f > 0: # 이렇게 조건 주는 게 좋음!
if slist[f] and slist[s]:
print(str(f) + " " + str(s))
break
else:
f -= 1
s += 1
for i in nlist:
check(i)
Author And Source
이 문제에 관하여([백준] 9020 : 골드바흐의 추측), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@letsbebrave/백준-9020-골드바흐의-추측저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)