기사단원의 무기

문제

문제 해석

1. 1부터 number까지 각각 숫자의 약수를 구한다.

2. 약수의 갯수가 limit을 넘어가는 경우 power를 answer에 더하고
3. 아닌 경우 약수의 갯수를 answer에 더한다.
4. 약수의 갯수는 1부터 해당 숫자까지 나누어서 나머지가 0인 수이다.
5. number가 100,000이므로 O(N^2)까지 괜찮다 생각했으나 시간초과가 발생한다.
6. O(logN)으로 푸는 방식(약수는 쌍을 이루므로 제곱근으로 제한을 둠)으로 푸니 시간제한을 통과할 수 있었다.

 

코드

#include <cmath>

using namespace std;

int solution(int number, int limit, int power) {
    int answer = 1;
    
    // 1부터 number까지 각각 숫자의 약수를 구한다.
    // 약수의 갯수가 limit을 넘어가는 경우 power를 answer에 더하고
    // 아닌 경우 약수의 갯수를 answer에 더한다.
    // 약수의 갯수는 1부터 해당 숫자까지 나누어서 나머지가 0인 수이다.
    // number가 100,000이므로 O(N^2)까지 괜찮다 생각했으나 시간초과가 발생한다.
    // O(logN)으로 푸는 방식(약수는 쌍을 이루므로 제곱근으로 제한을 둠)으로 푸니 시간제한을 통과할 수 있었다.
    
    int Attack = 1;
    int MaxVerify = 0;
    for(int Knight = 2; Knight <= number; ++Knight)
    {
        Attack = 0;
        MaxVerify = sqrt(Knight);
        
        for(int Test = 1; Test <= MaxVerify; ++Test)
        {
            if(Knight % Test == 0)
            {
                if(Knight / Test == Test) ++Attack;
                else Attack += 2;
            }
        }
        
        if(Attack > limit) answer += power;
        else answer += Attack;
    }    
    
    return answer;
}

 

다른 사람의 풀이

1. 제곱근 대신 위의 Test를 제곱하여 풀이