미소를뿌리는감자의 코딩
[백준 2024/09/07] 9020번 골드바흐의 추측 본문
728x90
1. 개요
https://www.acmicpc.net/problem/9020
2. 접근 방법
만약, 10이라는 짝수가 주어졌다고 가정해 보자.
그렇다면, 생성될 수 있는 possibilities는 다음과 같다.
2 + 8 = 10
3 + 7 = 10
4 + 6 = 10
5 + 5 = 10
6 + 4 = 10
7 + 3 = 10
8 + 2 = 10
이 가능할 것이다.
그 중,
2-8
8-2는 동일한 값이므로, 하나만 계산해 주면 된다.
5 + 5까지만 possibilities로 두면 되는 것이다. 따라서, n/2 + 1 까지만, 값을 비교하면 된다.
따라서, 2-8, 3-7, 4-6, 5-5에 대해서 두 수가 모두 소수인지 판단을 한 후, 소수라는 판단이 된다면 그 차를 두 수와 포함해서 리스트로 리스트에 저장해 둔다.
[ [ 두 수의 차, 수 1, 수2 ] ,[ 두 수의 차, 수 1, 수2 ], [ 두 수의 차, 수 1, 수2 ] ... ]
이런식으로 구성이 될 것이다.
이렇게 구성을 한 이유는 sort()를 통해 두 수의 차가 최소인 친구를 출력해 주기 위함이다.
3. 코드
import math
def find_decimal(arr):
for a in arr:
if a == 1:
return False
for i in range(2, int(math.sqrt(a))+1, 1):
if a % i == 0:
return False
return True
def find_possibilities(n):
possibilities = []
for i in range(2, int(n/2+1), 1):
if find_decimal([i, n-i]):
possibilities.append([n - 2 * i, i, n - i])
possibilities.sort()
return possibilities[0][1], possibilities[0][2]
def find_decimals(n):
for i in range(n):
a, b = find_possibilities(int(input()))
print("%d %d" % (a, b))
if __name__ == "__main__":
find_decimals(int(input()))
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/09/29] 1914번 하노이 탑 (0) | 2024.09.07 |
---|---|
[백준 2024/09/07] 10971번 외판원 순회 2 (1) | 2024.09.07 |
[백준 2024/09/07] 1978번 소수 찾기 (0) | 2024.09.07 |
[백준 2024/04/16] 2110번 공유기 설치 (0) | 2024.04.16 |
[백준 2024/04/03] 9663번 N-Queen (0) | 2024.04.05 |