[programmers] 소수 만들기 / C++

https://school.programmers.co.kr/learn/courses/30/lessons/12977

프로그래머스

 

#include <vector>
#include <iostream>
#include <math.h>

using namespace std;

int answer = 0;
int visited[1001];
int sel[10];

int isPrime(int num)
{
    if(num == 1) return 0;  // 소수 X
    
    int root = sqrt(num);
    for(int i=2; i<=root; i++)
    {
        if(num%i==0)
        {
            return 0; // 소수 X
        }
    }
    return 1; // 소수 O
}

void dfs(int start, int depth, vector<int> arr, int size)
{
    if(depth >= 3)
    {
        int sum = 0;
        for(int i=0; i<3; i++)
        {
            sum += sel[i];
        }
        if(isPrime(sum))
        {
            answer += 1;
        }
        return;
    }
    
    for(int i=start; i<size; i++)
    {
        if(!visited[i])
        {
            visited[i] = 1;
            sel[depth] = arr[i];
            dfs(i,depth+1, arr, size);
            visited[i] = 0;
        }
    }
    
}

int solution(vector<int> nums) {
    dfs(0,0,nums, nums.size());
    return answer;
}