소수만들기 C++(섬머/윈터코딩)[프로그래머스]

문제 주소입니다.

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

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

---

1. 문제 설명

2. 문제 해석

3. 소스 코드

4. 결과

---

1. 문제 설명

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

제한사항

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

예시

입출력 예

---

2. 문제풀이

1. dfs를 이용하여 숫자 3개를 더한 모든 수를 구한다. 2. 소수를 판별하여 카운트 3. 소수를 판단하기 위해서 squt를 사용했는데, 이렇게 하면 최대 연산량을 줄일 수 있다.

---

3. 소스코드

#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
 
vector<int> tempList;
 
bool primeNumber(int a) {
    for (int i = 2; i <= sqrt(a); i++)
        if (a % i == 0)//i가 나누어떨어지면 소수가 아님 
            return false;
    return true;
}
 
void serch(vector<int>& nums, int index = 0, int count=0, int sum = 0) {
    if (index >= nums.size())
        return;
    sum += nums[index];
    for (int i = index; i < nums.size(); i++) {
        if (count == 2) {
            tempList.push_back(sum);
            return;
        }
        else
            serch(nums, i+1, count+1, sum);
    }
}
 
int solution(vector<int> nums) {
    int answer = 0;
    for (int i = 0; i < nums.size()-2; i++)
        serch(nums, i);
    for (auto a : tempList) {
        if (primeNumber(a))
            answer++;
    }
    return answer;
}

 

---

4. 결과