[프로그래머스]서머코딩/윈터코딩(~2018) - 소수 만들기, C++

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

코딩테스트 연습 - 소수 만들기 | 프로그래머스

 본 문제는 서머 코딩/원터 코딩(~2018) 문제다. 소수 만들기라는 문제인데 주어진 숫자 중 3개의 수를 더해 소수를 만드는 문제다. 재귀 함수를 이용하여 문제를 해결하였다. 프로그래머스 LEVEL 2 문제 중 재귀 함수를 이용하면 쉽게 풀리는 문제가 많다. 몇 번 연습하다 보면 재귀 함수를 이용하는 문제를 쉽게 해결할 수 있다.

1. 해당 숫자를 선택할지 말지 결정
2. 3개의 숫자를 선택 완료
3. 소수 여부 확인

#include <vector>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int answer = 0;
 
bool chk(int n) {
    if (n < 2) return false;
    for (int i = 2; i*i <= n; i++) {
        if (n%i == 0) return false;
    }
    return true;
}
 
void dfs(vector<int> &nums, int index, int cnt, int sum) {
    // 숫자 3개 선택했을 때, 소수 확인
    if (cnt == 3) {
        if (chk(sum)) {
            answer += 1;
        }
        return;
    }
    if (nums.size() == index) return;
    // 숫자 선택 여부
    dfs(nums, index+1, cnt+1, sum + nums[index]);
    dfs(nums, index+1, cnt, sum);
}
 
int solution(vector<int> nums) {
    sort(nums.begin(), nums.end());
    dfs(nums, 0, 0, 0);
    return answer;
}