[코딩테스트 예제] 세 소수의 합
문제설명
어떤 수를 서로 다른 소수 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는 서로 다른 세 소수의 합으로 나타낼 수 없습니다.
내가 작성한 코드
## 조합을 사용하기위한 모둘 import
from itertools import combinations
def solution(n):
answer = 0
## 소수면 True를 담기위한 리스트
prime = [True]*n
# prime = []
prime[0] = False ## 1은 제외이므로
## n 까지의 소수를 모두 1로 표시
for i in range(2, int(n**0.5) + 1):
for j in range(2*i, n+1, i):
prime[j-1] = False
## True를 값으로 바꿈
L = [i+1 for i in range(n) if prime[i] == 1]
for i in combinations(L, 3):
if sum(i) == n:
answer += 1
return answer
위 문제를 처음 봤을 때 어떻게 풀어야하나 난감했다. 하지만 문제에서 가이드 해준대로 에라토스테스트의 체를 참고해서 이해하고 step함수 그리고 python에서 제공하는 조합(combinations) 모듈을 사용해 의외로 쉽게 해결할 수 있었다.
1. 에라토스테스트의 체
- 특정한 수 n 까지의 소수를 구하기위해서는 2부터 n의 제곱근 이하의 값까지의 모든 배수를 제거해나가면 n이하의 소수만 남게된다.
- step 함수 : range([strat,] stop [,step])
- start이상부터 stop미만까지의 수를 step 값의 간격?으로 전달한다.
## 예시
L = [i for i in range(1, 10, 2)]
print(L)
## 결과
[1,3,5,7,9]
- combination 모듈
python의 itertools 패키지에서는 순서가있는 순열(permutation)과 순서를 고려하지않는 조합(combinations) 모듈을 제공한다.
Author And Source
이 문제에 관하여([코딩테스트 예제] 세 소수의 합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dltjrdud37/코딩테스트-예제-세-소수의-합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)