[백준] 11502번 세 개의 소수 문제

💡문제접근

• 1부터 999까지의 수 중에서 소수를 만족하는 수를 에라토스테네스의 체를 이용하여 걸러내어 소수 리스트에 따로 저장해주었다. 그 다음 삼중 반복문을 통해서 입력값 K를 세 개의 소수의 덧셈으로 구현할 수 있으면 리스트에 저장하고 가능한 경우가 여러 가지라면 세 소수를 오름차순 정렬하라고 했기 때문에 key = lambda를 이용해서 정렬해주었다. 또한 가능하지 않다면 0을 출력하도록 코드를 작성했다.
• Python으로 제출했더니 계속 시간초과가 발생했다. 탐색 범위를 줄여보는 방법말곤 떠오르는 방법이 없어 PyPy3로 바꿔 제출했는데 AC를 받았다.

💡코드(메모리 : 181572KB, 시간 : 4536ms, PyPy3로 제출)

prime_number = [True] * 1000
prime_number[0] = False
prime_number[1] = False
li = []
for i in range(2, 1000):
    if prime_number[i]:
        li.append(i)
        for j in range(2*i, 1000, i):
            prime_number[j] = False

def prime_number_sum(x):
    result = []
    for a in range(len(li)):
        for b in range(len(li)):
            for c in range(len(li)):
                if li[a] + li[b] + li[c] == x:
                    result.append([li[a], li[b], li[c]])
    result = sorted(result, key = lambda x : (x[0], x[1], x[2]))
    if len(result) == 0:
        print(0)
    else:
        print(*result[0])

T = int(input())
for _ in range(T):
    K = int(input())
    prime_number_sum(K)

💡소요시간 : 27m