[프로그래머스 Level 1] 소수 만들기

문제

소수 만들기  

 

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

 

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

 

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

 

코드

#include <vector>
#include <iostream>
using namespace std;

int answer = 0;
vector<int> v;

void DFS(int now, int pos, int sum)
{
    if (now == 3)
    {
        for (int i = 2; i < sum; i++)
            if (sum % i == 0)
                return;

        answer++;
        return;
    }

    for (int i = pos; i < v.size(); i++)
        DFS(now + 1, i + 1, sum + v[i]);
}

int solution(vector<int> nums) 
{
    v = nums;

    DFS(0, 0, 0);

    return answer;
}

 

나의 생각

여러 숫자 중 세 개를 고르는 문제로 읽자마자 조합이 생각났다.

DFS로 조합을 구한 다음 소수인지 판별했다.