프로그래머스 - 136798번: 기사단원의 무기 [Java]

문제: https://school.programmers.co.kr/learn/courses/30/lessons/136798

프로그래머스

1. 코드

class Solution {
    public 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) {
                    cnt++;
                    if(i / j != j)
                        cnt++;
                }
            }
            answer += cnt <= limit ? cnt : power;
        }
        return answer;
    }
}

2. 설명

문제 해결 방법은 모든 수의 약수의 절반은 해당 수의 제곱근 이하인 점을 이용하여 문제를 해결하였습니다.

for(int j = 1; j * j <= i; j++) {
    if(i % j == 0) {
        cnt++;
        if(i / j != j)
            cnt ++;
    }
}

이 부분이 핵심인데 제곱근이 나온 예시를 들어 설명하면 10의 제곱근은 3.16227766017..이며 10의 약수는 [1, 2, 5, 10]이다. 그리고 약수의 총 개수에서 절반은 3이하의 수이다. 36의 경우에는 36의 제곱근은 6이며 36의 약수는 [1, 2, 3, 4, 6, 9, 12, 18, 36]으로 마찬가지로 총 개수에서 절반은 6이하의 수이다.

그리고 if( i / j ! = j)는 2 * 2 = 4, 3 * 3 = 9 와 같은 경우 나누었을 때 제수(divisor)와 몫이 동일하지만 다른 경우에는 약수가 2개이기에 추가적으로 증가시킵니다.

3. 정리

1. 어떤 수에 대한 약수의 절반은 제곱근 이하의 수들이다.

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges