문제
어떤 수를 서로 다른 소수 3개의 합으로 표현하는 경우의 수
n이 주어질 때 n을 서로 다른 소수 3개의 합으로 표현
n은 1,000이하의 자연수
입출력 예시
| n | return |
|---|---|
| 33 | 4 |
접근
2단계로 나누어서 푼다.
- n 이하의 소수 구하기
- 구한 소수들을 더하는 경우의 수 완전탐색하기
소수를 구하는 알고리즘은 에라토스테네스의 체 라는 알고리즘을 이용했다.
이 알고리즘은 간단하면서도 효과적이다.
2부터 시작하여 해당 수를 제외한 모든 배수를 체크하는 식으로 진행한다.
제외되는 수들은 따로 배열에 저장해두면, 이 배열이 소수들의 집합이다.
완전 탐색은 아직도 어떤게 좋은 코드인지 모르겠다.
항상 짜고나면 굉장히 코드가 지저분하게 느껴진다…
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def solution(n):
primeList = findPrime(n)
answer = BP(primeList, n, 0, 0, 0)
return answer
def findPrime(n):
check = [1] * n
primeList = []
for i in range(2,n):
if check[i]:
primeList.append(i)
for j in range(0, n, i):
check[j] = 0
return primeList
def BP(primeList, n, idx, sum, selectCnt):
if n < sum:
return 0
if selectCnt == 3:
if sum == n:
return 1
else:
return 0
if len(primeList) == idx:
return 0
return BP(primeList, n, idx+1, sum, selectCnt) +
BP(primeList, n, idx+1, sum + primeList[idx], selectCnt + 1)