LV2_소수 만들기(C++)

🚗문제 설명

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

🚓제한 조건

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

🚕입출력 설명

입출력 예 #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 <cmath>

using namespace std;

int answer = 0;
vector<int> val;

void dfs(int L, int sum, int cnt){
    
    //3개의 값을 통해 구한 값이 소수인지 아닌지를 판별
    if(cnt == 3){
        bool flag = true;
        for(int i = 2; i<=sqrt(sum); i++){
            if(sum%i == 0) {
                flag = false;
                break;
            }
        }
        
        //위 반복문에 안걸리면, 소수의 개수(answer)가 1 증가
        if(flag) answer += 1;
        return;
    }
    
    //다 돌았으면 해당 건은 종료한다.
    if(L == val.size()+1) return;
    
    else{
        //1. level 증가,
        //sum에 다음 노드의 값을 가지고 증가,
        //다음 노드 값을 사용하므로 cnt + 1
        dfs(L + 1, sum + val[L-1], cnt + 1);
        
        //2. level만 증가
        dfs(L + 1, sum, cnt);
    }
}

int solution(vector<int> nums) {
    val = nums;
    dfs(1, 0, 0);
    return answer;
}

---

• LV1에서 사용했던 에라토스테네스의 체를 이용해도 되긴 할 듯 하다.

• 3중 FOR문도 사용할 수 있었다. 하지만 DFS 이해해서 사용해보려고 노력했는데, 성과가 있었던 것 같아서 뿌듯하다.