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

문제 설명

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

 

제한 조건

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

 

입출력 예

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

 

 

코드

#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int is_prime(int n) {
    int i;
    
    if (n < 2)
        return 0;
    for (i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
            return 0;
    }
    return 1;
}

int solution(vector<int> nums) {
    int answer = 0;
    int i;
    int cnt;
    int tmp;
    vector<int> used;
    vector<int> n;
    
    while (i < nums.size() - 3)
    {
        used.push_back(0);
        i++;
    }
    while (i < nums.size())
    {
        used.push_back(1);
        i++;
    }
    do {
        i = 0;
        cnt = 0;
        tmp = 0;
        while (cnt < 3)
        {
            if (used[i])
            {
                tmp += nums[i];
                cnt++;
            }
            i++;
        }
        answer += is_prime(tmp);
    } while (next_permutation(used.begin(), used.end()));
    
    return answer;
}

 

3개의 숫자의 합이 소수인지 판별하는 문제이므로 고르는 숫자의 순서는 상관이 없다. nums와 같은 길이의 used 배열에 0과 3개의 1을 저장한다. 이 배열에 대해 가능한 모든 순열을 구하여 used의 1과 같은 인덱스에 있는 nums의 숫자들을 가지고 합을 구하여 그 결과가 소수인지 판별한다.

 

링크

코딩테스트 연습 - 소수 만들기

inbdni/Programmers