[백준 9506번] 약수들의 합(Java 풀이)

백준알고리즘 9506번 : 약수들의 합

 

주어진 숫자의 완전수 여부에 따라 적합한 문장을 출력해주면 되는 문제이다.

완전수라 함은 숫자 n이 자신을 제외한 모든 약수들의 합과 같은 것을 의미한다.

 

완전수가 맞는지, 아닌지 확인하기 위해 해야할 것은 우선 숫자 n의 모든 약수들을 구하고,

그 합을 계산해보는 것이다.

 

나는 1부터 숫자 n의 제곱근까지의 값까지 for문을 돌려 for문이 돌아가는 것을 최소화하려고 했다.

ArrayList에 값을 하나씩 추가한 뒤, 정렬을 하고,

가장 뒤에 있는 약수 n(이자 숫자 n)값은 없애주었다.

 

그리고 ArrayList내에 있는 약수들의 합이 n의 값과 같은지를 비교하고

결과에 따라 적절히 출력해주면된다.

 

 

 

풀이 과정

---

1. while문 내에 Scanner로 받는 값이 -1이 되면 멈출 수 있도록 break 구문을 넣는다.
2. ArrayList를 만든 뒤, 1부터 숫자 n의 제곱근까지 for문을 돌려 약수를 찾는다.
   약수를 찾는 동시에 약수들의 합을 담는 int 변수에 값들을 더한다.
3. ArrayList를 정렬하고, 마지막 값인 n 약수를 ArrayList 및 약수들의 합의 값에서 제외한다.
4. 약수들의 합이 n 값과 같다면, 정렬된 ArrayList를 출력한다.

 

 

 

소스 ▽

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		List<Integer> lst = new ArrayList<Integer>();

		while (true) {
			lst.clear();
			int num = sc.nextInt();
			int sum = 0;

			if (num == -1) {
				break;
			}
			for (int i = 1; i <= Math.sqrt(num); i++) {
				if (num % i == 0) {
					lst.add(i);
					lst.add(num / i);
					sum += i + num / i;
				}
			}
			sum -= num;
			if (sum == num) {
				System.out.print(num + " = 1");
				Collections.sort(lst);
				for (int i = 1; i < lst.size()-1; i++) {
					System.out.print(" + " + lst.get(i));
				}
				System.out.println();
			} else {
				System.out.println(num + " is NOT perfect.");
			}

		}

	}
}

 

 

 

Summary

---

1. ArrayList x의 정렬 : Collections.sort(x);
2. 숫자 num의 제곱근 : Math.sqrt(num);