소수 만들기

문제

 

문제 해석

- 소수의 정의 : 1과 자기 자신으로만 나눌 수 있는 수

- nums에 들어있는 숫자 3개를 뽑아 더하므로 조합을 만들 필요가 있다. (next_permutation, vector<bool> 사용)

- 1~1000 이하의 자연수이므로 O(N^2)까지 괜찮다 생각했다.

- vector<bool>을 이용하기 위해 미리 nums - 3개로 벡터의 크기를 정하고 next_permutation을 사용할 것이므로 true를 마지막에 채워준다.

- vector<bool>을 매번 반복마다 순회하여 true인 경우 숫자 합계에 더해준다.

- 매번 반복마다 소수인지 체크하고 소수라면 소수인 경우의 수를 증가시킨다.

 

- 에라토스테네스의 체를 이용하여 푼다면 미리 1~3000까지의 숫자가 소수인지 판별한다.(배열 선언)

- n의 배수인 수를 n~(3000-1)까지 반복하며 소수가 아님을 체크한다.(false 처리)

- 미리 에라토스테네스의 체를 수행한다.

- Sum에 해당하는 배열의 값이 true인지 확인하고 맞다면 소수인 경우의 수를 증가시킨다.

 

코드

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

// 소수의 정의 : 1과 자기 자신으로만 나눌 수 있는 수
/*
bool IsPrime(int InNumber)
{
    // 1이면 소수가 아니므로 거짓이다.
    if(1 == InNumber)
        return false;
    
    bool Result = true;
    // 만약 2라면 자기 자신으로 나눌 수 있으므로 참이다.
    // 2부터 N까지 자기 자신 이전까지의 수로 나눌 수 있는지 순회로 검사한다.O(N)
    int Limit = InNumber - 1;
    for(int Number = 2; Number < Limit; ++Number)
    {
        if(InNumber % Number == 0)
        {
            Result = false;
            break;
        }
    }
    
    return Result;
}
*/

// 에라토스테네스의 체 사용
constexpr int MAX_SUM = 3001;
// 최대 3000이므로 1~3000까지라 가정하고 판별 
bool Primes[3001];

void IsPrime()
{
    fill(Primes, Primes + MAX_SUM, true);
    
    for(int Number = 2; Number < MAX_SUM; ++Number)
    {
        if(0 == Primes[Number])
            continue;
        
        for(int Multiple = Number + Number; Multiple <= MAX_SUM; Multiple += Number)
            Primes[Multiple] = false;
    }
}



int solution(vector<int> Nums) {
    int Answer = 0;
    // 주어진 숫자 중 "3개의 수를 더했을 때" 소수가 되는 경우의 개수
    // 제한사항 
    // 숫자의 개수는 3개 이상 50개 이하
    // 각 원소는 1 이상 1,000 이하
    
    // 조합을 사용하면 되는데 vector<bool>로 처리하는게 편리하므로 이를 사용하자
    vector<bool> Using;
    // 주어진 숫자들 - 3개만큼을 미리 만들어준다
    Using.resize(Nums.size() - 3);
    for(int Iter = 0; Iter < 3; ++Iter)
    {
        Using.push_back(true);
    }

    // 숫자 3개를 더한 임시값
    int Sum = 0;
    int UsingSize = static_cast<int>(Using.size());
    // 에라토스테네스의 체를 미리 사용한다.
    IsPrime();
    
    // 알고리즘을 사용해 조합을 만든다.
    do
    {
        Sum = 0;
        // 50개 이하이므로 시간 복잡도는 O(N^2)도 괜찮으리라 판단된다.
        for(int IDX = 0; IDX < UsingSize; ++IDX)
        {
            if(Using[IDX])
            {
                Sum += Nums[IDX];
            }
        }
        
        // 소수인지를 판별한다.
        //if(IsPrime(Sum))
        //{
        //    ++Answer;
        //}
        
        // 에라토스테네스의 체에서 걸러진 소수인 경우 합계가 소수이므로 판별된 소수 개수를 증가시킨다.
        if(Primes[Sum])
        {
             ++Answer;
        }
    } while(next_permutation(Using.begin(), Using.end()));

    return Answer;
}

 

다른 사람의 풀이

1. 삼중 for문을 이용한 풀이, 더 변수를 적게 사용하는 소수 체크방법

 

회고

1. 에라토스테네스의 체를 배운 것이 좋았던 문제

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

에라토스테네스의 체