[알고리즘 문제] 세 소수의 합 (Python / 파이썬)

문제

유니는 오늘 한가지 퀴즈를 받았다.
"홀수 N을 세 개의 소수의 합으로 나타내는 경우의 수는 몇가지 있을까?"
여기서 소수란 2, 3, 5 ,7 처럼 약수의 개수가 정확히 두 개인 수를 말한다.
세 개의 소수의 합으로 나타내는 경우의 수를 셀 때는 더하는 수의 순서를 바꾼 것은 같은 경우로 세고, 같은 소수를 여러번 더해도 된다. 예를들어 7을 세 소수의 합으로 나타낸다면 2 + 2 + 3 처럼 2를 두 번 사용해서 나타내는 것도 가능하다. 또한, 2 + 2 + 3과 3 + 2 + 2, 2 + 3 + 2는 모두 같은 경우이므로 이것들은 한번만 세야 한다.
유니를 도와서 N을 세 개의 소수의 합으로 나타내는 경우의 수를 구하는 프로그램을 만들어보자.

입력

첫째 줄에 테스트케이스의 수 T가 주어진다..
각 테스트케이스의 첫 줄에 N이 주어진다.
( 1 ≤ T ≤ 10, 1 ≤ N ≤ 999 ) 

출력

각 테스트케이스마다 '#'과 테스트케이스의 번호, 공백을 출력한 뒤 N을 세 개의 소수의 합으로 나타내는 방법의 수를 출력한다.

---

문제 풀이

처음엔 이 문제를 재귀 함수를 이용해 풀이했습니다.

하지만 시간 초과 문제가 발생해 다른 방법을 이용해야 했습니다.

 

어떤 홀수 N이 주어졌을 때 세 개의 소수의 합으로 나타내야 하며

같은 수를 중복해 사용 가능하나 순서가 바뀐 것은 동일한 것으로 간주해야 합니다.

따라서 일단 소수가 무엇인지 알아야 하므로 소수를 모두 구해

따로 Prime 배열에 넣어주었습니다.

세 소수의 합이 될 수 있는 조합을 모두 찾아야 하므로 3중 for문을 이용했습니다.

이때 중복은 가능하나 오름차순이 되도록 조합해야 하므로 

두 번째, 세 번째 for문은 각각 이전 for문의 index부터 시작하도록 해주었습니다.

 

이렇게 조건에 따른 모든 조합을 탐색하며 합이 N이 될 때만 수를 count 해주면

답을 찾을 수 있습니다. 

---

My Code

# 소수를 모두 찾아줌 
MAX = 1000

check = [True] * MAX 
check[1] = False
for i in range(2, MAX):
    for j in range(i + i, MAX, i):
        check[j] = False

# 찾은 소수들을 따로 배열에 넣어줌
prime = []
for i in range(1, MAX):
    if check[i]:
        prime.append(i)

for tc in range(int(input())):
    n = int(input()) # 홀수 N

    # 오름차순인 세 개의 소수 중 합이 N이 되는 것 찾아 count (중복 허용)
    count = 0
    for i in range(len(prime)):
        for j in range(i, len(prime)):
            for k in range(j, len(prime)):
                if prime[i] + prime[j] + prime[k] == n:
                    count += 1

    print('#' + str(tc + 1), end = ' ')
    print(count)