[백준 2024/09/07] 9020번 골드바흐의 추측

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()))