소수가 되는 경우 카운팅 (재귀호출)

문제를 보는 순간 모든 경우를 다 계산해봐야된다고 생각해서 재귀호출로 해결하고자 했다.

근데 초기 작성 코드에서 결과 값이 기댓 값 보다 많이 커서 원하지 않는 중복이 발생했다고 생각했다.

이를 해결하기 위해 고민하다가, 시작 인덱스를 매개변수로 추가적으로 전달해서 현재 인덱스보다 큰 인덱스를 탐색하도록 했다.

 

 

*초기 작성 코드 (오류 있음)

#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

int Check_PrimeNum(int sum)
{
    for (int i = 2; i <= sqrt(sum); ++i)
    {
        if (sum % i == 0) return 0;
    }
    return 1;
}

void Count_PrimeNum(const vector<int>& nums, vector<int>& used, int& result, int sum, int count)
{
    if (count == 3)
    {
        result += Check_PrimeNum(sum);
        return;
    }

    for (int i = 0; i < nums.size(); ++i)
    {
        if (used[i] == 1) continue;

        used[i] = 1;
        sum += nums[i];

        Count_PrimeNum(nums, used, result, sum, count + 1);

        used[i] = 0;
        sum -= nums[i];
    }
}

int solution(vector<int> nums) {

    int result = 0;
    vector<int> used(nums.size());

    Count_PrimeNum(nums, used, result, 0, 0);


    return result;
}

• 기대 값이 '4' 인데 결과 값이 '24'가 나온 상황이다.
• 디버깅을 해본 결과, 중복된 인덱스를 선택하지 않기 위해 used배열을 활용하긴 했으나, 재귀호출하면서 전에 선택했던 경우를 중복 선택하는 상황이 발견되었다.
• used배열을 사용할게 아니라, 다음 선택은 이전에 선택한 인덱스보다 높은 인덱스 값을 선택해야 된다고 인지하였다.

 

*수정된 코드

#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

// 소수인지 확인 메서드
int Check_PrimeNum(int sum)
{
    for (int i = 2; i <= sqrt(sum); ++i) // 2 ~ sum의 루트까지 나눈 나머지가 0이 발생하면 소수X
    {
        if (sum % i == 0) return 0;
    }
    return 1; // 루프 통과하면 소수O
}

void Count_PrimeNum(const vector<int>& nums, int start, int& result, int sum, int count)
{
    if (count == 3) // 3개의 수 선택
    {
        result += Check_PrimeNum(sum);
        return;
    }

    for (int i = start; i < nums.size(); ++i) // 시작 인덱스 1씩 증가
    {
        Count_PrimeNum(nums, i + 1, result, sum + nums[i], count + 1);  
    }
}

int solution(vector<int> nums) {

    int result = 0;
    int start = 0;

    Count_PrimeNum(nums, start, result, 0, 0);

    return result;
}

int solution(vector<int> nums) {

    int result = 0;
    vector<int> used(nums.size());

    Count_PrimeNum(nums, used, result, 0, 0);

    return result;
}

• used 배열 대신, 시작 인덱스 start를 매개변수로 전달했다.
• 재귀호출 시에 이전의 시작 인덱스보다 높은 인덱스에서 시작하기 때문에, 중복된 경우를 발생하지 않게 할 수 있었다.