[Programmers - S/W coding 2018] 소수 만들기 (cpp / python)

소수 만들기

프로그래머스

 

문제 설명

주어진 숫자들 중 3개를 골라 더하여 소수인지 판별하는 문제

에라토스테네스의 체를 이용하여 문제를 해결한다.

문제 풀이

소스코드 : C++

1. 숫자의 범위의 최대는 1000이므로 나올 수 있는 가장 큰 값은 1000 + 999 + 998 이다. 따라서 대략 3000개의 숫자에 대해서 모든 소수를 찾는다.
2. 에라토스테네스의 체를 이용하여 2~ 3000까지의 소수를 판별한다.
3. 조합을 구현하여 N개 중 3개를 선택한다.
4. 모두 더하여 소수인지 판별한다.

#include<iostream>
#include <vector>
#include <iostream>
using namespace std;
const int MAX = 3001;
int prime[3000];// ture :  소수가 아니다
vector<int> Nums;
vector<int> v;
vector<int> visit;
int answer;
void checkPrimeNum() {
    prime[0] = true;
    prime[1] = true;

    int i = 2, j = 2;
    while (i*j < MAX) {
        for (int j = 2; j*i < MAX; j++)
            if (!prime[i*j])prime[i*j] = true;
        i++;
    }
}
void process(int i, int cnt) {
    if (cnt == 3) {
        int res = 0;
        for (int k = 0; k < v.size(); k++) 
            res += v[k];
        if (!prime[res]) answer++;
        return;
    }
    for(int j=i; j<Nums.size(); j++){
        if (!visit[j]) {
            visit[j] = true;
            v.push_back(Nums[j]);
            process(j, cnt + 1);
            v.pop_back();
            visit[j] = false;
        }
    }
}
int solution(vector<int> nums) {
    Nums = nums;
    visit.assign(nums.size(), 0);
    checkPrimeNum();
    process(0, 0);
    return answer;
}

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

int answer;
bool chk_prime(int x){
    for(int i=2; i*i<=x; i++)
        if(x%i==0)return false;
    return true;
}
void process(vector<int> &nums,vector<bool> &chk, int i, int cnt, int sum){
    if(cnt>3)return;
    if(cnt == 3){
        if(chk_prime(sum))
            answer++;
        return;
    }
    for(int j =i; j<chk.size(); j++){
        if(!chk[j]){
            chk[j] =true;
            process(nums,chk, j, cnt+1 , sum + nums[j]);
            chk[j] = false;
        }
    }
}
int solution(vector<int> nums) {
    int n = nums.size();
    vector<bool> chk(n);
    process(nums,chk,0,0,0);

    return answer;
}
int main(){
    cout<<solution({1,2,7,6,4});
    return 0;
}

소스코드 : Python

재귀를 이용하지 않고 4개 이상의 조합을 구현을 하려면 어떻게 해야할까...

answer =0
def chk_prime(x):
    i = 2
    while(i*i<=x):
        if x%i == 0: return False
        i+=1
    return True
def process(nums,chk,i,sum,cnt):
    if cnt>3: return
    if cnt == 3 and chk_prime(sum):
        global answer
        answer+=1
        return
    for j in range(i,len(nums)):
        if not chk[j] :
            chk[j] = True
            process(nums, chk, j, sum + nums[j],cnt +1)
            chk[j] = False

def solution(nums):
    global answer
    n = len(nums)
    chk = [0]*n
    process(nums, chk,0,0,0)
    return answer