Level 1. 기사단원의 무기

Level 1. 기사단원의 무기

 

 

약수의 개수를 효율적으로 구하는 것이 중점인 문제였다.

 

나는 num의 제곱근만큼 순회하면서 나머지 연산을 이용해 계산하였다.

 

#include <iostream>
#include <cmath>

using namespace std;

int getNumberOfDivisor(int num)
{
    int last = sqrt(num);
    int count = (pow(last, 2) == num) ? -1 : 0;

    for (int i = 1; i <= last; ++i)
        if (num % i == 0)
            count += 2;

    return count;
}

int solution(int number, int limit, int power)
{
    int answer = 0;

    do
    {
        int count = getNumberOfDivisor(number);

        answer += (limit < count) ? power : count;
    }
    while (--number);

    return answer;
}

 

내 방법이 가장 간단한 줄 알았는데 훨씬 단순한 방법이 있었다.

 

매번 num의 약수의 개수를 계산하는 것이 아니라, num까지의 모든 약수의 개수를 계산하여 vector에 저장하는 방법이 있었다.

 

또, 이중 for문을 순회하면서 1씩 더해 계산한다.

 

약수의 개수 = 자신을 배수로 갖는 수의 개수를 이용한 것이다.

 

하지만, 성능은 아마 내 방법이 더 좋을 것이다.

 

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

using namespace std;

vector<int> countDivisors(int num)
{
    vector<int> divisorCounts(num + 1, 0);

    for (int i = 1; i <= num; ++i)
        for (int j = i; j <= num; j += i)
            ++divisorCounts[j];

    return divisorCounts;
}

int solution(int number, int limit, int power)
{
    int answer = 0;
    vector<int> divisorCounts = countDivisors(number);

    do
        answer += (limit < divisorCounts[number]) ? power : divisorCounts[number];
    while (--number);

    return answer;
}