파이썬 알고리즘-80 (BOJ 9020) 골드바흐의 추측

문제

내 코드

# 에라토스테네스의 체로 소수를 구현하기 위해 체크배열과 소수를 담을 배열 작성
ch=[0]*10001
sosu=[0]*10001
for i in range(2,10001):
    if ch[i]==0:
        sosu[i]=i
        for j in range(i,10001,i):
            ch[j]=1

n=int(input())
for _ in range(n):
    i=int(input())
    # 입력의 중간값부터 시작
    left=i//2
    while left>1:
        # 오른쪽은 결국 입력값-왼쪽일 때만 입력값이 만들어지므로 이렇게 하면 모든 경우를 구할 필요 없이 입력값이 만들어지는 경우만 볼 수 있음
        right=i-left
        # 둘 다 소수일 경우에만 답을 구함
        if sosu[left]>0 and sosu[right]>0:
            # 중간부터 시작하는 것이 차이가 가장 작으므로 둘 다 소수이면서 합이 입력값이 된다면 바로 break 가능
            res=[sosu[left], sosu[right]]
            break
        else:
            left-=1
        
    print(res[0], res[1])

소감

투포인터 알고리즘을 사용하는 문제였는데 익숙하지 않아 접근을 제대로 하지 못했다.
처음에는 왼쪽부터 시작해 하나씩 늘려가는 방식을 썼는데 조건을 잘 맞추면 답은 나오지만 숫자가 커지기 시작하면 구해야 되는 경우의 수가 늘어나므로 시간초과가 떴다.
다음에는 왼쪽은 처음부터 오른쪽은 끝에서부터 시작해서 더한 값이 크면 오른쪽을 -1 작으면 왼쪽을 +1 하는 방식을 썼는데, 마찬가지로 경우의 수가 늘어나면서 시간초과가 뜨고, 문제에서 요구하는 것은 차이가 가장 작은 것을 출력하라는 것이었으므로 비효율적이었다.