[백준] 9506번 : 약수들의 합 – JAVA [자바]

https://www.acmicpc.net/problem/9506

9506번: 약수들의 합

 

---

• 문제

 

 

---

• 문제 풀이

백준 9506번 약수들의 합은 브론즈 1 난이도의 수학 및 구현 문제이다. 이 문제에서는 각 입력마다 정수 n이 주어지고 이 n이 완전수라면 n을 약수들의 합으로 나타내서 출력하면 되고 n이 완전수가 아닐 경우, " n is NOT perfect."를 출력하면 된다. 여기서 완전수는 n의 약수들을 다 더했을 때, 이 합이 n이 되는 것을 뜻한다.

 

우선 main 함수 말고 추가 함수인 getDivisor 함수를 만들었다. 이 함수는 정수 n의 약수들을 리스트로 반환하는 역할을 한다. 단, 약수들의 합이 n이 아닐 경우, 즉 n이 완전수가 아닐 경우에는 리스트 대신 null을 반환한다. 추가로, 정수 n의 약수들을 효율적으로 구하려면 for-loop을 1부터 n까지가 아닌, 1부터 n의 제곱근까지만 해주면 된다. 이렇게 하면 시간 복잡도가 O(N)이 아닌, O(√N)으로 구현할 수 있다. 추가로, 리스트를 반환하기 전에 리스트를 오름차순으로 정렬을 하고 반환해 준다.

 

main 함수에서는 while loop을 통해서 정수 n들을 입력받는다. 그리고 n이 -1일 경우에는 입력이 끝났다는 것을 뜻하기 때문에 while loop을 종료해 준다. 우선 미리 만들었던 getDivisor 함수를 통해서 정수 n의 약수들을 리스트 형태로 받는다. 만약에 이 리스트가 null일 경우, 완전수가 아니므로 "n is NOT perfect."를 출력해 준다. 리스트가 null이 아닐 경우에는 완전수이므로 이 리스트에 있는 숫자들을 합의 형태로 출력해 주면 된다.

 

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == -1) break;  //-1을 입력 받으면 입력 종료
            List<Integer> list = getDivisor(n);
            if (list == null) {
                sb.append(n + " is NOT perfect.\n");
                continue;
            }
            sb.append(n + " = ");
            for (int i = 0; i < list.size() - 1; i++) {
                sb.append(list.get(i) + " + ");
            }
            sb.append(list.get(list.size() - 1) + "\n");
        }
        System.out.print(sb);

    }

    //정수 n의 약수들을 구해서 약수들을 리스트로 반환. 단, 약수들의 합이 n이 아닐 경우, null 반환.
    public static List<Integer> getDivisor(int n) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        int total = 1;

        // 약수들을 효율적으로 구하려면 n의 제곱근까지만 하면 된다.
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                list.add(i);
                list.add(n / i);
                total += i + (n/i);
            }
        }
        if (total != n) return null;
        Collections.sort(list);
        return list;
    }
}