문제
접근
주어지는 수 중 순서에 상관없이 3개를 뽑는 문제로, 완전 탐색 문제이다.
소수를 미리 다 찾아두고 3개의 합이 소수인지 확인만 해주면 된다.
코드
- 파이썬 코드
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
dp = [1] * 3000
def solution(nums):
answer = -1
dp[0] = dp[1] = 0
for i in range(2, 3000):
if dp[i] != 1:
continue
for j in range(i*2, 3000, i):
dp[j] = 0
answer = bf(0, 0, 0, nums)
return answer
def bf(now, cnt, sumNum, nums):
ans = 0
if cnt == 3:
if dp[sumNum] == 1:
return 1
else:
return 0
for i in range(now, len(nums)):
ans += bf(i+1, cnt+1, sumNum+nums[i], nums)
return ans