문제 설명
어떤 수를 서로 다른 소수 3개의 합으로 표현하는 경우의 수를 구하려 합니다. 예를 들어 33은 총 4가지 방법으로 표현할 수 있습니다.
- 3+7+23
- 3+11+19
- 3+13+17
- 5+11+17
자연수 n이 매개변수로 주어질 때, n을 서로 다른 소수 3개의 합으로 표현하는 경우의 수를 return 하는 solution 함수를 작성해주세요.
제한 조건
- n은 1,000 이하인 자연수입니다.
입출력 예
n | return |
---|---|
33 | 4 |
9 | 0 |
입출력 예 설명
예시 #1 문제에 나온 예와 같습니다.
예시 #2 9는 서로 다른 세 소수의 합으로 나타낼 수 없습니다.
나의풀이
첫번째 풀이
소스
def get_prime_list(n):
num_list = [True] * n
m = int(n ** 0.5)
for i in range(2, m + 1):
if num_list[i]:
for j in range(i+i, n, i):
num_list[j] = False
return [i for i in range(2, n) if num_list[i]]
def solution(n):
answer = 0
prime_list = get_prime_list(n)
prime_num = len(prime_list)
for i in range(prime_num-2):
for j in range(i+1, prime_num-1):
for k in range(j+1, prime_num):
if prime_list[i] + prime_list[j] + prime_list[k] == n:
answer += 1
return answer
설명
- 소수를 구하는 공식인, 에라토스테네스의 체를 사용.
- 주어진 n에 대하여 소수 리스트를 구한다.
- 해당 리스트에서 나올 수 있는 경우의 수를 모두 구한 후 결과값이 n과 같으면 정답 1씩 더해주는 방식.
- 에라토스테네스의 체는 외워두자.
- 조합을 직접 구하였는데 itertools의 combinations를 사용하자.
결과
통과
리뷰
- 오퍼레이터 사이는 띄워쓰는 것이 좋습니다. (m = int(n ** 0.5))
조합을
combinations
함수를 통해 쉽게 구할 수 있습니다. :)from itertools import combinations ... answer = [sum(i) for i in list(combinations(prime_list, 3))].count(n)