기사단원의 무기(프로그래머스)

기사단원의 무기(programmers)

풀이

• 효율적인 약수를 구해주는 방법을 사용해야한다(시간초과 해결)
• 약수의 경우, 해당 숫자의 제곱근까지 약수를 구한 후, 구한 약수들을 숫자에 나눈 후, 중복되는 값이 있는지 확인 하며 삽입을 진행하는 것이 효율적이다.

코드

#include <string>
#include <vector>
#include <unordered_set>
#include <cmath>
using namespace std;

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

    //약수를 구해준다.
    for (int i = 1; i <= number; ++i)
    {
        int cnt = 0;
        for (int j = 1; j * j <= i; ++j)
        {
            if (i % j != 0)
                continue;

            int share = i / j;
            if (share == j) cnt += 1;
            else cnt += 2;
        }


        if (cnt > limit)
            answer += power;
        else
            answer += cnt;
    }

    return answer;
}