[프로그래머스/c++] 소수 만들기

 

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

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

 

#include <iostream>
#include <vector>
using namespace std;

int cnt = 0;
bool visited[51];

bool checkPrime(int n){
    if(n <= 1) return false;
    if(n == 2) return true;

    //만약에 나눴는데 0이 나오면 소수 아님
    for (int j=2; j<n; j++) if (n % j == 0) return false;
    return true;
}

void rf(vector<int> n, int k, int s, int sum){
    if(k == 3){
        if(checkPrime(sum)) cnt++;
        return;
    }

    for(int i=s; i<n.size(); i++){
        if(!visited[i]){
            visited[i] = true;
            rf(n, k+1, i+1, sum+n[i]);
            visited[i] = false;
        }
    }
}

int solution(vector<int> nums) {
    int answer = -1;
    rf(nums, 0, 0, 0);
    answer = cnt;
    return answer;
}

 

재귀 함수로 nums 배열의 숫자를 3개씩 중복 없이 뽑아줬다. 중복 없이 하기 위해서 visited 배열을 사용했고, 그리고 s 매개변수를 통해 시작점을 잡아줬다. 이렇게 하지 않으면 (1, 2, ?) 개씩 뽑는 것에서 넘어가서 (1, 3, ?)에서 (1, 3, 2)를 뽑아버리기 때문에 이를 방지하기 위해서 (1, 3, ?)에서 ? 부분은 3 뒤의 원소를 사용하지 못하도록 막아준 것이다.

3개의 숫자를 모두 뽑았다면, 소수인지 확인하는 함수 (checkPrime(n)) 에서 소수라는 판정이 나오면 카운팅해줬다.