[프로그래머스] 소수 만들기 c++

문제 설명

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

제한 사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

입출력 예

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

풀이

다른 사람들이 푼 풀이들도 봤는데 이중for문, 삼중 for문 등등 for문을 이용해서 푼거 같았다.

나는 이 문제를 dfs로 풀었다. 

 

PrimeNum함수는 소수를 판별하는 함수이다.

dfs는 check배열로 방문 표시하였다. 배열 중 3개가 true인지 확인하고, true인 배열 원소들을 더한다.

이 때 더한 값이 소수인지 판별하고 소수라면 reuslt 값을 +1 한다.

#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

bool check[51];
int result = 0;

const bool PrimeNum(int n){
    for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0) {
			return false;
		}
	}
	return true;
}

void dfs(int l , int s, vector<int> nums){
    if( l == 3){
        int sum = 0;
        for(int i = 0; i < nums.size(); i++){
            if(check[i]){
                sum += nums[i];
            }
        }
        if(PrimeNum(sum)){
            result++;
        }
    }
    else{
        for(int i = s; i < nums.size(); i++){
            check[i] = true;
            dfs(l+1, i+1, nums);
            check[i] = false;
        }
    }
    
}

int solution(vector<int> nums) {
    int answer = -1;
    
    dfs(0,0, nums);
    
    answer = result;

    return answer;
}