1단계 / 136798 / 기사단원의 무기

문제 설명

---

코드

class Solution {
    public int solution(int number, int limit, int power) {
        int ans = 0;

        for (int i = 1; i <= number; i++) {
            int offensePower = 0;
            for (int j = 1; j * j <= i; j++) {
                if (j * j == i) offensePower++;
                else if (i % j == 0) offensePower += 2;
            }
            
            if(offensePower <= limit) ans += offensePower;
            else ans += power;
        }
        
        return ans;
    }
}

Error

시간초과 오류가 발생했다.

원인

이중 for문 탓!

해결

약수의 개수를 구하는 안쪽 for문을 제곱근을 이용하여 시간을 단축시켰다.
약수의 개수를 구하려는 수 N의 한 약수가 i일 때,

• 제곱근 i 가 존재할 경우 약수의 개수를 하나씩 더한다.
• 그 외의 경우 N/i 또한 N의 약수일테니 개수를 둘 씩 더한다.