[코딩 테스트/ 백준 알고리즘] 1037번 : 약수 (Java 풀이)

문제

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

1037번: 약수

---

문제 설명

---

문제 풀이

 약수의 성질을 사용하면 쉽게 풀 수 있는 문제다.

 어떤 수 A가 어떤 수 C의 약수라면, C / A = B인 B도 C의 약수라는 것이다.

수	진짜 약수의 개수	진짜 약수
12	4	2, 3, 4, 6
24	6	2, 3, 4, 6, 8, 12
121	1	11

 12의 경우

• 12 % 2 = 0이기 때문에 2는 12의 약수다. 
• 12 / 2 = 6이고, 12 % 6 = 0이기 때문에 6는 12의 약수다.

24의 경우

• 24 % 2 = 0이기 때문에 2는 24의 약수다.
• 24 / 2 = 12이고, 24 % 12 = 0이기 때문에 12는 24의 약수다.

 가장 작은 약수와 가장 큰 약수가 대응되기 때문에, 가장 작은 약수와 가장 큰 약수를 곱한 값이 구하고자 하는 수 N이 된다.

---

코드

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int arr[] = new int[k];
        int count = 0;
        
        while(sc.hasNext()) {
            arr[count++] = sc.nextInt();
        }
        Arrays.sort(arr);	//약수 정렬
        System.out.println(arr[0] * arr[k - 1]);	//가장 큰 값과 작은 값 곱해서 출력
    }
}

---

총평

 생각하게 만드는 문제였다.