소수 만들기

문제의 조건에 n = 50이기 때문에 완전탐색으로 충분히 풀 수 있는 문제이다.

그런데 주의할 점은 재귀로 구현하면 시간초과가 발생한다.. 코드의 시간복잡도는 50^3 * sqrt(3000)일텐데, 어째서 시간 초과가 발생하는지는 결국 알 수 없었다.

그래서 3중for문으로 수정하였다.

재귀로 작성한 코드

#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
#define PRIME 1
#define NOT_PRIME 2
int result = 0;
vector<int> v;
int dp[3000] = { 0, };
bool IsPrime(const vector<int>& picked)
{
	int sum = 0;
	for (const auto& item : picked)
		sum += item;

	if (dp[sum] == PRIME)
		return true;
	else if (dp[sum] == NOT_PRIME)
		return false;
	else if (sum % 2 == 0) {
		dp[sum] = NOT_PRIME;
		return false;
	}

	for (int i = 3; i <= sqrt(sum); i += 2) {
		if (sum % i == 0) {
			dp[sum] = NOT_PRIME;
			return false;
		}
	}
	dp[sum] = PRIME;
	return true;
}
void bf(int n, vector<int>& picked, int toPick, int idx)
{
	if (toPick == 0 && IsPrime(picked)) {
		result++;
		return;
	}
	int smallest = picked.empty() ? 0 : idx + 1;
	for (int next = smallest; next < n; ++next) {
		picked.push_back(v[next]);
		bf(n, picked, toPick - 1, next);
		picked.pop_back();
	}
}
int solution(vector<int> nums) {
	v = nums;
	vector<int> picked;
	bf(nums.size(), picked, 3, 0);
	return result;
}

3중 for문으로 작성한 코드

#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
#define PRIME 1
#define NOT_PRIME 2
int result = 0;
int dp[3000] = {0, };
bool IsPrime(int sum)
{   
    if(dp[sum] == PRIME)
        return true;
    else if(dp[sum] == NOT_PRIME)
        return false;
    else if(sum % 2 == 0){
        dp[sum] = NOT_PRIME;
        return false;
    }
    
    for(int i = 3; i <= sqrt(sum); i += 2){
        if(sum % i == 0){
            dp[sum] = NOT_PRIME;
            return false;
        }
    }
    dp[sum] = PRIME;
    return true;
}
int solution(vector<int> nums) {
    int size = nums.size();
    for(int i=0; i<size; i++){
        for(int j=i+1; j<size; j++){
            for(int k=j+1; k<size; k++){
                int num = nums[i] + nums[j] + nums[k];
                if(IsPrime(num)) result++;
            }
        }
    }
    return result;
}