[프로그래머스/C++]Lv.1 - 소수 만들기

문제 링크

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

내 풀이

모든 더하는 경우의 수를 소수인지 검사한다.

내 코드

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

bool check(int num)
{
    for(int i = 2; i * i <= num; i++)
    {
        if(num/i * i == num)
            return false;
    }
    return true;
}

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

    for(int i = 0; i < nums.size() - 2; i++)
    {
        for(int j = i + 1; j < nums.size() -1; j++)
        {
            for(int k = j + 1; k < nums.size(); k++)
            {
                if(check(nums[i]+nums[j]+nums[k]))
                    answer++;
            }
        }
    }

    return answer;
}

다른 사람의 풀이

#include <vector>
#include <algorithm>
using namespace std;
#define MAXSUM 3001
bool prime[3001]; //1000이하의 자연수이므로

//소수 구하기는 에라토스테네스의 방법을 사용한다
void CheckPrime(){
    fill(prime, prime+MAXSUM, 1);
    for(int i = 2;i < MAXSUM;i++){
        if(prime[i] == 0) continue;
        for(int j = i+i;j <= MAXSUM;j += i)
            prime[j] = 0;
    }
}
/*
void Combination(vector<int> &nums, int pos, int r, int sum, int &answer){
    if(r == 0){ //3개를 다 선택함
        if(prime[sum]){
            answer++;
            return;
        }
    }
    if(pos == nums.size()) return; //끝까지 확인함

    Combination(nums, ++pos, r, sum, answer); //현재 숫자를 선택하지 않음
    sum += nums[pos-1]; //하나를 선택함
    Combination(nums, pos, --r, sum, answer);   
}
*/

void Combination(vector<int> nums, int &answer){
    int sum = 0;
    int s = nums.size();
    vector<int> per(s-3);
    for(int i = 0;i < 3;i++) per.push_back(1);

    do{
        sum = 0;
        for(int i = 0;i < per.size();i++)
            if(per[i] == 1) sum += nums[i];
        if(prime[sum]) answer++;
    }while(next_permutation(per.begin(), per.end()));
}


int solution(vector<int> nums) {
    int answer = 0; int pos = 0;
    int sum = 0; int r = 3;

    CheckPrime();
    Combination(nums, answer);
    return answer;
}

다른 사람의 풀이 해석

소수판별시 에라토스테네스의 체 방법을 사용하였다.