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

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

프로그래머스

풀이

재귀와 약수 판단 알고리즘을 사용해서 간단히 해결할 수 있습니다.

다른 분들의 풀이가 for문으로 많이 작성되어 있길래 한번 포스트 해보았습니다.

#include <vector>
#include <iostream>

using namespace std;

int answer;

void dfs(int L, int idx, int sum, vector<int> nums) 
{
    if (L == 3) {
    	// 약수 판별 
        for (int i=2; i*i<=sum; i++) {
            if (sum % i == 0)
                return;
        }
        answer++;
        return;
    }        
    else {
    	// 순열
        for (int i=idx; i<nums.size(); i++) {
            dfs(L+1, i+1, sum+nums[i], nums);
        }
    }
}

int solution(vector<int> nums) {
    
    dfs(0, 0, 0, nums);
    
    return answer;
}