[Summer/Winter Coding(~2018)] 소수 만들기

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

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

[c++]

  nums 배열의 원소 3개로 만들 수 있는 합이 소수인 경우를 카운트하는 것이다. 이때 주의할 점은 합에 대한 중복 처리는 하지 않아도 된다. 왜냐면 소수 P 가 만약에 각각 다른 원소의 합으로 구성된다면, 숫자는 같지만 다른 경우이다. 더불어 각각의 원소는 중복되지 않는다는 전제가 있으므로 합에 대한 중복처리는 신경쓰지 않아도 된다.

 

  nums 배열의 원소를 순회하며 3가지를 선택하여 만들 수 있는 합을 구하는 방법으로 백트래킹을 사용하였다. depth(k), start 인덱스, nums 배열을 인자로 받는 dfs 함수에서 k 가 3 이라면 3 가지의 원소를 모두 택한 것이므로 sum 을 구하고, isprime 함수에 sum 을 넣어 소수인지 판별한다.

 

  k 가 3이 아니라면 아직 3 가지의 원소를 모두 택한 것이 아니므로 start index 부터 num.size() 까지 for 문을 돌며 arr 배열에 차곡차곡 nums[i] 를 저장한다. 그리고 dfs(k+1, i+1, nums) 를 재귀호출하면 arr 배열에는 결국 선택된 3가지 원소가 arr[0], arr[1], arr[2] 에 저장된다. 이를 더한 값이 sum 이다.

 

  sum 의 소수 판별은 자신을 제외한 나누어 떨어지는 수가 없는지 확인하는데, 대칭성에 의해 소수 판별에는 지장이 없으므로 범위를 sqrt(sum) 까지만 수행하여 연산량을 줄였다.

 

#include <vector>
#include <math.h>
#include <iostream>
using namespace std;


bool isused[100];
int sum = 0; int ans = 0;
vector<int> arr(3, 0);

bool isprime(int n)
{
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

void dfs(int k, int start, vector<int>& nums)
{
    if (k == 3)
    {
        sum = arr[0] + arr[1] + arr[2];
        if (isprime(sum))
        {
            ans++;
            sum = 0;
        }
        return;
    }
    else
    {
        for (int i = start; i < nums.size(); i++)
        {
            arr[k] = nums[i];
            dfs(k + 1, i + 1, nums);
        }

    }
}


int solution(vector<int> nums) {

    dfs(0, 0, nums);

    return ans;
}