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

문제

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

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

풀이

백트래킹으로 해결할 수 있었다. nums의 모든 요소에 대해 n개 중 3개를 뽑는 조합을 만들어주고 조합이 완성되면 소수 판별 함수를 통해 소수인지 아닌지 판별해주었다.

코드

#include <vector>

using namespace std;

int result = 0;
int arr[1001];
bool isused[1001];

bool isPrimeNumber(int n)
{
    if (n == 1)
    {
        return false;
    }
    else if (n == 2)
    {
        return true;
    }

    for (int i = 3; i <= n - 1; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}

void func(int idx, int cnt, vector<int> nums)
{
    int temp = 0;

    if (cnt == 3)
    {
        for (int i = 0; i < 3; i++)
        {
            temp += arr[i];
        }
        if (isPrimeNumber(temp))
        {
            result++;
        }
        return;
    }

    for (int i = idx; i < nums.size(); i++)
    {
        if (!isused[nums[i]])
        {
            isused[nums[i]] = true;
            arr[cnt] = nums[i];
            func(i + 1, cnt + 1, nums);
            isused[nums[i]] = false;
        }
    }
}

int solution(vector<int> nums) {

    int answer = -1;

    func(0, 0, nums);

    answer = result;

    return answer;
}