소수만들기

문제설명

입출력예 및 설명

 

=> DFS를 사용하여 풀 수 있는 문제입니다. 

 

=> DFS를 사용하며 시작하는 INDEX를 하나씩 늘려가며 중복되는 수의 조합은 제외하였습니다. 

 

=> DFS를 사용하며 Parameter들의 값이 실제로 올라가는 것인지, 넘기는 값만 올라가는 것인지, 주소를 참조하는 것인지 등을 잘 판단하여 써야 합니다. 

 

=> 소수인지를 판별하는 함수를 생성하여 소수를 판별하여 전역변수에 소수 여부를 기록하였습니다. 

      *1은 소수가 아니며 2는 소수이므로 미리 표시해둡니다. 

 

=> 시간초과의 경우에 걸리지 않도록 return문을 잘 넣어줍니다. 

 

 if(cntAdd == 3)
    {
        if(prime[sum]) 
        {
            cnt++;return;
        }
        Prime(sum);
        if(prime[sum]) 
        {
            cnt++;
        }
        return;
    }

=> 해당부문에서 return을 잘못 넣어 시간 초과가 걸렸습니다. 

 

 

#include <vector>
#include <iostream>
#include <cmath>
using namespace std;

bool prime[3001];
bool check[51];

int cnt=0;

void Prime(int tmp)
{
    for(int i=2; i<sqrt(tmp)+1; i++)
    {
        if(tmp%i ==0)
        {
            prime[tmp]=false;
            return;
        }
    }
    prime[tmp]=true;
}

void dfs(int index,int sum,  int cntAdd, vector<int>& nums)
{
    if(cntAdd == 3)
    {
        if(prime[sum]) 
        {
            cnt++;return;
        }
        Prime(sum);
        if(prime[sum]) 
        {
            cnt++;
        }
        return;
    }
    
    for(int i= index; i<nums.size(); i++)
    {
        if(!check[i])
        {
            check[i] = true; 
            dfs(i,sum+nums[i],cntAdd+1, nums);
            check[i] = false;
        }
    }
}

int solution(vector<int> nums) {
    int answer = -1;

    prime[1]= false; prime[2]=true;
    dfs(0,0, 0, nums);
    answer = cnt;
    return answer;
}