[프로그래머스] LV.1 기사단원의 무기 - Java [53/80]

💬 문제 설명

숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다.

각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.

예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다. 무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다. 그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.

기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 return 하는 solution 함수를 완성하시오.

 

🚫 제한 사항

• 1 ≤ number ≤ 100,000
• 2 ≤ limit ≤ 100
• 1 ≤ power ≤ limit

 

📢 입출력 예

 

👨‍🏫 입출력 예 설명

 

📃 제출 코드

class Solution {
    public int solution(int number, int limit, int power) {
        int[] knights = new int[number];
        
        for (int i = 0; i < knights.length; i++) {
            int count = 0;
            for (int j = 1; j <= Math.sqrt(i + 1); j++) {
                if (j * j == (i + 1)) count++;
                else if ((i + 1) % j == 0) count+=2;
            }
            knights[i] = count;
        }
        
        int answer = 0;
        for (int i : knights) {
            answer += i <= limit ? i : power;
        }
        
        return answer;
    }
}

 

✏ 해결방법 & 배운점

약수의 개수를 구하기 위해서 주어진 정수의 제곱근까지만 검사해도 된다는것을 알았습니다.

++) 배운점 정리

어떤 수 $n$의 약수는 일반적으로 쌍을 이루게 된다 즉 $n$의 약수는 $(a,b)$와 같이 두 개씩 묶을 수 있으며,

$a * b = n$ 이된다. 예를 들어, $n = 12$ 인경우

$n = 12$ 일때 약수는 1, 2, 3, 4, 6, 12이다. 즉 (1,12), (2,6), (3, 4)와 같은 쌍을 이루게 된다.

 

하지만 $n$이 제곱수 인경우 약수 가운데 하나는 제곱근이 된다. 이경우는 쌍이 맞지 않는다.

$n = 16$ 일때 약수는 1, 2, 4, 8, 16이다. 즉 (1,16), (2,8) (4, 4)와 같이 가운데 제곱근이 포함되어있다. 

$n$이 제곱수인 경우 약수의 개수는 홀수가 되고 제곱수가 아닌경우는 약수의 개수가 짝수가 된다.

 

즉, 어떤수 $n$의 제곱근까지만 검사를 하게 된다면 약수의 개수를 알 수 있다.

예) $n = 36$일때 약수의 개수를 구하는 소스코드

36의 약수 : 1, 2, 3, 4, 6, 9, 12, 18, 36 이다. 즉 (1, 36), (2, 18), (3, 12), (4, 9), (6, 6) 쌍을 이룬다.

int number = 36;
int count = 0;
for (int i = 1; i <= Math.sqrt(number); i++) {
	if (i * i == number) count++;
	else if (number % i == 0) count += 2;
}

 

위 코드에서 Math.sqrt() 메서드는 제곱근을 구하는 메서드로, Math.sqrt(36)은 6을 반환합니다.

따라서 i의 값은 1부터 6까지 증가하며 반복됩니다.

1. 반복문:
   • for (int i = 1; i <= Math.sqrt(number); i++) { ... }
   • i는 1부터 6까지의 값을 가지며 반복됩니다.
2. 제곱근 확인:
   • if (i * i == number) count++;
   • 만약 i * i가 number와 같다면, 이는 i가 number의 제곱근임을 의미합니다.
   • 예를 들어, i가 6일 때, $6*6 = 36$ 이므로 count 변수가 1 증가합니다.
   • 이는 제곱근이 하나의 고유한 약수임을 나타냅니다.
3. 약수 쌍 확인:
   • else if (number % i == 0) count += 2;
   • 만약 number % i가 0이라면, 이는 i가 number의 약수임을 의미합니다.
   • 예를 들어, i가 2일 때, $36 mod 2 = 0$ 이므로 count 변수가 2 증가합니다.
   • 이는 i와 number / i가 각각 약수이므로 두 개의 약수를 추가합니다.
     • i = 2,  number / 2 = 18 즉 (2, 18) 2개 쌍을 이루므로 2를 증가시킵니다.