프로그래머스 약수의 개수와 덧셈 (JAVA)

🔗 문제 링크

프로그래머스 약수의 개수와 덧셈

---

📌 문제 개요

두 정수 left, right 사이의 숫자들을 순회하면서 최종 결과를 반환하는 문제

• 약수 개수가 짝수 → 더하기
• 약수 개수가 홀수 → 빼기

처음에는 약수를 직접 구해서 개수를 세는 방식으로 접근했지만,
문제의 핵심 규칙을 발견하면 훨씬 간단하게 해결할 수 있다.

---

📌 접근 방법

완전제곱수는 약수 개수가 홀수

 

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

예를 들어 12의 약수는 이렇게 짝으로 존재하므로 약수 개수는 짝수가 된다.

1 × 12
2 × 6
3 × 4

 

하지만 완전제곱수인 16 처럼 루트 값이 자기 자신과 겹친다.

1 × 16
2 × 8
4 × 4

혼자 남기 때문에 약수 개수가 홀수가 된다.

4

---

📌 핵심 아이디어

완전제곱수 판별은 다음처럼 가능하다.

int sqrt = (int)Math.sqrt(num);

sqrt * sqrt == num

 

• Math.sqrt() 로 제곱근 계산
• 다시 제곱했을 때 원래 값과 같으면 완전제곱수

따라서 아래 방식으로 해결 할 수 있다.

• 완전제곱수 → 빼기
• 나머지 → 더하기

---

📌 전체 코드

package level1;

public class No25 {

    public static void main(String[] args) {
        int left = 24;
        int right = 27;
        int sum = 0;

        for (int i = left; i <= right; i++) {

            // 완전제곱수면 약수 개수 홀수
            if (isPerfectSquare(i)) {
                sum -= i;
            } else {
                sum += i;
            }
        }

        System.out.println(sum);
    }

    public static boolean isPerfectSquare(int num) {
        int sqrt = (int) Math.sqrt(num);
        return sqrt * sqrt == num;
    }
}

 

---

📄 정리

이 문제는 단순 구현 문제처럼 보이지만
수학적 특징을 알고 있으면 훨씬 쉽게 해결할 수 있는 문제

(학창시절에 수학 공부좀 할껄..)

완전제곱수 <=> 약수 개수 홀수

관계를 이해하는 것이 핵심이었다.

약수를 직접 계산하는 방법도 가능하지만,
완전제곱수 판별을 이용하면 더 효율적이고 깔끔하게 구현할 수 있다.