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

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

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

문제 설명

---

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 구하시오.

 

접근 방식

---

그리디를 활용하여 3개의 합을 모두 구해서 소수의 개수를 구했습니다.

 

코드

---

#include <vector>
#include <iostream>
using namespace std;
int total=0,ans=0;
void gd(int cnt,int idx,vector<int> nums){
    if(cnt==3){
        int flag=0;
        for(int i=2;i<total;i++){
            if(total%i==0){
                flag=1;break;
            }
        }
        if(flag==1)return;
        else {ans++;return;}
    }
    //0 1 2 3 2 3 1 2 3
    else{
        for(int i=idx;i<nums.size();i++){
            total+=nums[i];
            gd(cnt+1,i+1,nums);
            total-=nums[i];
        }
    }
}
int solution(vector<int> nums) {
    int answer = -1;
    gd(0,0,nums);
    answer=ans;
    return answer;
}

funny algorithm 0_<