[백준] 1153번 네 개의 소수

💡문제접근

• 4중 반복문을 통해서 소수 4개를 가져오는 방식으로 코드를 작성했다.
• Python3로는 시간초과(TLE)가 나와서 PyPy3로 제출했는데 AC를 받았다. 그런데 맞힌 사람들의 메모리와 시간을 보니 정말 하늘과 땅 차이였다. 머릿속에 떠오르는 방법은 4중 반복문 밖에 없어서 이 방법을 사용한건데 더 좋은 방법이 있는걸까?

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

import sys
input = sys.stdin.readline

def solve(x):
    prime = []
    arr = [True] * (N+1)
    arr[0] = False
    arr[1] = False
    for i in range(2, N+1):
        if arr[i]:
            prime.append(i)
            for j in range(i*i, N+1, i):
                arr[j] = False

    flag = False
    for a in prime:
        if flag:
            break
        for b in prime:
            if flag:
                break
            for c in prime:
                if flag:
                    break
                for d in prime:
                    if a + b + c + d > N:
                        break
                    if a + b + c + d == N:
                        flag = True
                        ans = f"{a} {b} {c} {d}"
                        break
    if flag == False:
        return -1
    return ans

N = int(input())
print(solve(N))

💡소요시간 : 10m