[프로그래머스/Java] 기사단원의 무기

-Code

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        int cnt;
        for (int i = 1; i <= number; i++) {
            cnt = measureCount(i);
            answer += cnt <= limit ? cnt : power;
        }
        return answer;
    }

    public static int measureCount(int n) {
        int cnt = 0;
        for (int i = 1; i <= Math.sqrt(n); i++) {
            cnt += n % i == 0 ? (n / i != i ? 2 : 1) : 0;
        }
        return cnt;
    }
}

처음에는 1, n까지 모두 검사를 했으나 시간 초과로 틀렸습니다. 그래서 공식을 찾아보니 제곱근을 이용하는 방법을 찾게되었고 다음과 같습니다.

1~n까지를 검사할때 예를 들어 n이 24면 1, 2, 3, 4, 6, 8, 12, 24인데 각각 1 * 24, 2 * 12, 3 * 8, 4 * 6으로 묶어서 값을 2개씩  찾는게 가능합니다. 하지만, n이 16처럼 1, 2, 4, 8, 16과 같은 경우 1 * 16, 2 * 8, 4 * 4로 되어서 같은 값의 제곱인 경우 즉,  n / i == i 에는 값을 1만 더해줘야합니다.