프로그래머스 기사단원의 무기 JAVA 풀이 (약수, 구현)

🔗 문제 링크

프로그래머스

 

---

📌 문제 개요

숫자나라 기사단의 기사들은 1번부터 number번까지 번호를 가진다.

각 기사는 자신의 번호의 약수 개수만큼 공격력을 가진 무기를 구매한다.

 

다만 약수 개수가 제한 수치 limit을 초과하면, 정해진 공격력 power를 가진 무기를 구매해야 한다.

무기의 공격력 1당 철 1kg이 필요하므로, 모든 기사에게 필요한 철의 총합을 구하는 문제

---

📌 접근 방법

1번 기사부터 number번 기사까지 순회한다.

각 기사 번호 i에 대해 약수 개수를 구한다.

 

약수는 1부터 i까지 전부 확인할 필요 없이 j * j <= i 범위까지만 확인한다.

j가 i의 약수라면 j와 i / j를 함께 카운트한다.

 

단, j와 i / j가 같은 경우는 완전제곱수이므로 한 번만 카운트한다.

약수 개수를 구한 뒤 limit을 초과하면 power를 더하고, 아니면 약수 개수를 더한다.

---

📌 핵심 아이디어

약수는 보통 쌍으로 존재한다.

예를 들어 10의 약수는 다음과 같다.

1 × 10
2 × 5

그래서 1과 2까지만 확인해도 10, 5를 함께 찾을 수 있다.

하지만 9처럼 완전제곱수인 경우는 다르다.

1 × 9
3 × 3

이때 3은 한 번만 세어야 하므로 아래 조건이 필요하다.

if (j != i / j) {
    count++;
}

 

---

📌 전체 코드

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

        for (int i = 1; i <= number; i++) {
            int count = 0;

            for (int j = 1; j * j <= i; j++) {
                if (i % j == 0) {
                    count++;

                    if (j != i / j) {
                        count++;
                    }
                }
            }

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

        return answer;
    }
}

---

📄 정리

이 문제는 각 숫자의 약수 개수를 구한 뒤 조건에 따라 값을 누적하는 문제이다.

약수를 구할 때 제곱근까지만 탐색하면 불필요한 반복을 줄일 수 있다.

 

또한 완전제곱수의 경우 같은 약수가 중복으로 카운트되지 않도록 주의