Problem
https://www.acmicpc.net/problem/9020
Solution
오답코드1 (시간초과)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import sys
# 소수 탐색
def prime_list(n):
sieve = [True] * n
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i] == True:
for j in range(i+i, n, i):
sieve[j] = False
return [i for i in range(2, n) if sieve[i] == True]
# 골드바흐 파티션 구하기
def solve(n):
j = 0
arr = {} # 모든 파티션을 저장할 딕셔너리
sosu = prime_list(n)
while sosu[j] <= (n//2): # 소수가 n/2 이하인 경우
if n-sosu[j] in sosu:
arr[sosu[j]] = n-sosu[j]
j += 1
min = n
x, y = 0, 0
for k, v in arr.items(): # 차이가 최소인 파티션 찾기
if abs(k - v) < min:
min = abs(k - v)
x, y = k, v
return x, y
t = int(input())
for i in range(t):
n = int(sys.stdin.readline())
x,y = solve(n)
print(x,y)
n 미만의 소수 중에서 합이 n이 나오는 모든 쌍을 찾아 딕셔너리에 저장 후 차이가 최소인 파티션을 리턴해 출력하는 코드이다.
오답코드2 (시간초과)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys
# 소수 탐색
def prime_list(n):
sieve = [True] * n
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i] == True:
for j in range(i+i, n, i):
sieve[j] = False
return [i for i in range(2, n) if sieve[i] == True]
# 골드바흐 파티션 구하기
def solve(n):
j = 0
sosu = prime_list(n)
while sosu[j] <= (n//2): # 소수가 n/2 이하인 경우
if n-sosu[j] in sosu:
x, y = sosu[j], n-sosu[j]
j += 1
return x, y
t = int(input())
for i in range(t):
n = int(sys.stdin.readline())
x,y = solve(n)
print(x,y)
1번 코드에서 마지막으로 구한 파티션은 결국 차이가 최소인 파티션이기 때문에(n/2 이하인 소수만 찾았으므로) 따로 딕셔너리에 저장해서 비교하지 않고 바로 리턴했다.
정답코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys
# 소수 탐색
def prime_list(n):
sieve = [True] * n
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i] == True:
for j in range(i+i, n, i):
sieve[j] = False
return [i for i in range(2, n) if sieve[i] == True]
# 골드바흐 파티션 구하기
def solve(n):
sosu = prime_list(n)
j = len(sosu)-1
while sosu[j]> n//2: # 소수가 n/2 초과인 경우
j-=1
while 1:
if n-sosu[j] in sosu:
x, y = sosu[j], n-sosu[j]
break
j -= 1
return x, y
t = int(input())
for i in range(t):
n = int(sys.stdin.readline())
x,y = solve(n)
print(x,y)
위의 2번과 같은 방식의 코드이지만 이번에는 소수를 중간부터 찾아서 내려오는 방식으로 짰다. 어쨌든 차이가 최소가 되려면 (x, y)값에서 x가 제일 큰 경우를 찾아야 하기 때문에 큰 값부터 찾는게 효율적이기 때문이다.