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

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

https://school.programmers.co.kr/learn/courses/30/lessons/12977?language=cpp' 

프로그래머스

---

 

 

 

 

 

 

제한 사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

---

 

 

 

 

 

 

풀이

문제를 풀기 위해서는 두 가지 알고리즘이 필요하다.

1. 주어진 배열의 원소로 조합 만들기
2. 소수 판별

소수 판별은 이렇다 할 알고리즘 없이 2부터 나누어 떨어지는 수가 있는지 확인해야 한다.

최적화를 하자면 나누어 떨어지는 수를 찾는 것이기에 cmath::sqrt를 이용하여 제곱근까지의 수만 확인해도 된다. 

조합을 만드는 알고리즘은 순열, 조합, 부분집합을 참고하면 된다.

---

 

 

 

 

 

전체 코드

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


int comb(vector<int>& nums, vector<int>& temp, int depth)
{
    if(temp.size() == 3)
    {
        int sum = temp[0] + temp[1] + temp[2];
        
        // 소수 판별
        bool flag = true;
        for(int i = 2; i <= sqrt(sum); i++)
        {
            if(sum % i == 0) flag = false;
        }
        
        return flag;
    }
    
    // 조합
    int cnt = 0;
    for(int i = depth; i < nums.size(); i++)
    {
        temp.push_back(nums[i]);
        cnt += comb(nums, temp, i+1);

        temp.pop_back();
    }
    
    return cnt;
}


int solution(vector<int> nums) {
    int answer = -1;
    vector<int> temp;
    
    answer = comb(nums, temp, 0);

    return answer;
}

---