[프로그래머스 12977] - 소수 만들기

문제출처

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

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

 

문제풀이

재귀 함수를 이용해 숫자의 합을 구한뒤 소수 판별을 해주면 되는 간단한 문제

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%86%8C%EC%88%98%20%EB%A7%8C%EB%93%A4%EA%B8%B0.cpp

sw93/algorithm

 

#include <vector>
#include <cmath>
using namespace std;
int ans = 0;
bool checkPrime(int number) {
    if (number == 1) return false;
    if (number == 2) return true;
    for (int i=2; i<=sqrt(number); i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}
void go(vector<int> nums, int startIdx, int depth, int sum) {
    if (depth == 3) {
        if (checkPrime(sum)) {
            ans++;
        }
        return;
    }
    for (int i=startIdx; i<nums.size(); i++) {
        go(nums, i+1, depth+1, sum+nums[i]);
    }
}
int solution(vector<int> nums) {
    go(nums, 0, 0, 0);
    
    return ans;
}