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

성공 코드(내 코드)

• DFS를 이용하여 주어진 숫자 중 3개를 선택하는 경우의 수를 구하였다.
• 각각의 경우마다 선택된 숫자 3개의 합을 구하고 해당 수가 소수인지 판별하였다.

#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
vector<int> arr, ch(50, 0);
int cnt=0;

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

void DFS(int s, int L){
    if(L==3){
        int sum=0;
        for(int i=0; i<3; i++){
            sum+=ch[i];
        }
        if(isPrime(sum)){
            cnt++;
        }
    } else{
        for(int i=s; i<arr.size(); i++){
            ch[L]=arr[i];
            DFS(i+1, L+1);
        }
    }
}

int solution(vector<int> nums) {
    arr=nums;
    DFS(0, 0);
    
    return cnt;
}

 

---

다른 사람 코드

• 3중 for문을 이용하여 각각의 경우마다 세 수를 더하여 해당 수가 소수인지 판별하였다.

#include <vector>
#include <iostream>
using namespace std;
bool check(int n){
    for(int i=2;i<n/2;i++)
        if(n%i==0)
            return false;
    return true;
}
int solution(vector<int> nums) {
    int answer = 0;
    int N=nums.size();
    for(int i=0;i<N;i++)
        for(int j=i+1;j<N;j++)
            for(int k=j+1;k<N;k++){
                if(check(nums[i]+nums[j]+nums[k]))
                    answer++;
            }
    return answer;
}