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

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

코딩테스트 연습 - 소수 만들기

---

 

-풀이-

먼저 dfs를 이용하여 3종류의 숫자의 합을 만든다. 그런 뒤, 만들어진 합의 소수판별여부를 확인하여 answer를 갱신한다.

 

-코드-

#include <vector>
#include<cmath>
#include <iostream>
using namespace std;
int answer=0;

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

void dfs(int now,int sum,int cnt,vector<int>& nums){
    if(cnt==3){
        if(check(sum)) answer++;
        return;
    }
    for(int i=now+1;i<nums.size();i++){
        dfs(i,sum+nums[i],cnt+1,nums);
    }
}

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