[PY] 9020 : 골드바흐의 추측

https://www.acmicpc.net/problem/9020

 

 

얘 진짜 당황스러운 문제였다. 힌트로는 에라스토테네스의 체를 제시하길래 나무위키에서 찾은 내용대로 구현을 했다.
테스트 케이스들에 대해서도 작동이 좋았으니 잘 되겠거니 하고 백준에 던졌는데,

시간 초과!!!!!!!!

그래서 주변에 묻고 힌트를 얻으려해보니 그냥 문제를 한번 다시 봐보라는 이야기를 하더라.
주어지는 입력은 짝수였고 2로 나눠도 나머지가 없다.
그럼 나눠진 숫자를 다시 더해도 내용은 같다는거고 어쨌든 두 갈래로 값이 나뉘었을 때
하나가 적어진 만큼 다른 하나가 커지면 어쨌든 내용은 똑같은 것이다.

결론은 주어지는 숫자를 가져와서 2로 나눈 다음에 소수인지 아닌지를 체크해 나간다.
소수가 아니면 숫자를 조금씩 바꾼다. 한쪽은 1을 내리고 한쪽은 1을 올린다. 그리고 가장 먼저 발견되는 숫자 쌍이 정답이다.
왜냐하면 차이가 적은 답을 가져와야 하는데, 가장 먼저 발견되는 쌍이 제일 차이가 적은 답이기 때문이다.

다음엔 더 입체적으로 문제를 볼 수 있도록 해보려고 한다.

<기존에 구상한 코드>

#past code
from math import sqrt
from sys import stdin

array = list(range(1, 10001))
squareRoot = sqrt(10000)


for i in range(int(squareRoot)):
    if i == 0 or i == 1:
        continue
    isNotPrime = False
    for j in range(2, i):
        # range가 i라는건 어쨌든 i - 1 까지인거니까 의미있는 소수 판정이 가능하다
        if i % j == 0:
            isNotPrime = True

        if isNotPrime:
            break
        # i라는 숫자 하나에 대해 모든 숫자를 대조해서 비교하니, 
        # 중간에 소수가 아님이 확인된다면 바로 그만 둘 수 있도록 한다.

    # 이쪽 영역에 들어오면 백프로 소수이다.
    for j in range(2, (int(squareRoot) // i) + 1):
        # squareRoot 숫자를 넘어가지 않도록 하기 위함이다. 즉 i가 7이면 sqR // i는 14가 나오겠지, 하지만 range는 해당 숫자 직전에서 끝내기 때문에
        # + 1을 끝 점에 지정한다. 그리고 * 1 이 계산되면 안되기때문에 명시적으로 2를 적는다.
        delTargetIdx = i * j - 1
        array[delTargetIdx] = -1
        # array[0] = 1이 들어있으니, 내가 뺴야하는 값에서 - 1을 해야 빼야하는 값의 위치가 잡힌다.

# 이거 array가 어쨌든 길이가 가변성이니 문제가 생길 수 있겠다.
a = 0
while a < len(array):
    if array[a] == -1:
        del array[a]
    else:
        a += 1

# 여기서 모든 소수 목록의 결과를 확인 할 수 있다.
# 에라토스 뭐시기의 체는 구현 완료

# 그럼 소수만 있는 Pool에서 전개를 해나가야한다.
# 입력된 숫자의 범위 이상 직전
    # 즉 8이 입력되면 8은 소수 7보다 크고 소수 11보다 작으니 7까지의 범위를 제한하고
    # 여기서 더해질 수 있는 모든 쌍을 얻어야한다.
    # 쌍을 얻고나면 두 차가 제일 작은 경우가 답이 된다.

caseNum = int(stdin.readline())


for i in range(caseNum):
    resultList = []
    minVal = 10000000
    minIdx = 0

    targetNum = int(stdin.readline())
    isFounded = False
    defIdx = 0

    for j in range(len(array)):
        # targetNum이랑 비교해서 범위를 찾아내야한다.
        if targetNum <= array[j]:
            isFounded = True
            defIdx = j - 1
            break

    for j in range(defIdx):
        for k in range(defIdx):
            if targetNum == array[j] + array[k]:
                resultList.append([array[j],array[k]])

    for idx, pair in enumerate(resultList, start=0):
        result = abs(pair[0] - pair[1])

        if minVal > result:
            minVal = result
            minIdx = idx

    print(str(resultList[minIdx][0]) + " " + str(resultList[minIdx][1]))

<문제 정독 후 정정된 코드>

#after code
from sys import stdin

def isPrimeNum(num):
    if num <= 1:
        return False

    if num == 2:
        return True

    for i in range(2, num):
        if num % i == 0:
            return False

    return True


caseNum = int(stdin.readline())

for i in range(caseNum):
    targetNum = int(stdin.readline())
    targetA = targetNum // 2
    targetB = targetA


    minVal = 1000000
    minIdx = 0

    while targetA != 1:
        if isPrimeNum(targetA) and isPrimeNum(targetB):
                print(str(targetA) + " " + str(targetB))
                break

        targetA -= 1
        targetB += 1