[프로그래머스/C++ 문제 풀이] Lv. 1 - 소수 만들기

문제 설명

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

제한 사항

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

입출력 예

 

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

 

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

---

문제 풀이

이번 문제는 주어진 숫자들 중 3개를 뽑아 합을 구하고, 해당 값이 소수인지를 판별하는 문제입니다.

 

주어진 nums 배열에서 3개를 무작위로 뽑기 위해 3중 for문을 사용하여 3개의 값을 뽑는 방법도 있으나, 저의 경우 완전탐색 알고리즘을 사용해 3개의 값을 추출하였으며 소수인 경우 카운트를 증가시키는 방식으로 문제를 해결하였습니다.

정답 코드

풀이 시간 : 2m 56s

#include <vector>

using namespace std;

vector<int> v;
int cnt;

// 소수 판별 함수
bool Check(const vector<int>& v)
{
    int sum = 0;
    
    for (int n : v)
    {
        sum += n;
    }
    
    for (int i = 3; i < sum; i++)
    {
        if (sum % i == 0)
        {
            return false;
        }
    }
    
    return true;
}

// 완전탐색
void Go(const vector<int>& nums, int n)
{
    // 기저사례
    if (v.size() == 3)
    {
        // 만약 3개의 합이 소수인 경우
        if (Check(v))
        {
            // 카운트 증가
            cnt++;
        }
        
        return;
    }
    
    // n부터 nums배열의 크기까지 순회
    for (int i = n; i < nums.size(); i++)
    {
        // v에 num[i] 추가
        v.push_back(nums[i]);
        // 재귀
        Go(nums, i + 1);
        // v의 마지막 요소 삭제 
        v.pop_back();
    }
}

int solution(vector<int> nums) {
    
    Go(nums, 0);
    
    return cnt;
}