[알고리즘C++]소수 만들기

오늘의 문제

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

소수 만들기

나의 풀이

#include <vector>
#include <iostream>
using namespace std;
vector<int> per(3);                             
int count = 0;                         
bool check[51] = { false, };   

void permutation(int depth, vector<int> num, int idx){ 
    if(depth == 3){
        int sum = 0;
        for(int i=0;i<3;i++){
            sum += per[i];
        }
        
        for(int i = 2;i<sum;i++){
            if(sum%i ==0)
                break;
            if(i == sum-1)
                count++;
        }
        return;
    }
    for(int i = idx; i < num.size(); i++){
        if(!check[i]){
            check[i] = true;
            per[depth] = num[i];
            permutation(depth + 1, num, i+1);    
            check[i] = false;             
        }
    }
}
    
int solution(vector<int> nums) {
    permutation(0, nums, 0);
    return count;
}

모범 답안

#include <vector>
#include <iostream>
using namespace std;
bool check(int n){
    for(int i=2;i<n/2;i++)
        if(n%i==0)
            return false;
    return true;
}
int solution(vector<int> nums) {
    int answer = 0;
    int N=nums.size();
    for(int i=0;i<N;i++)
        for(int j=i+1;j<N;j++)
            for(int k=j+1;k<N;k++){
                if(check(nums[i]+nums[j]+nums[k]))
                    answer++;
            }
    return answer;
}

배울 점

• 이사람은 곧바로 3중for문을 사용했고만 조합이니까 얼마 안나오니 가능할 것 같다