[백준] java 1037 약수

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

문제

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

풀이과정

A가 N의 진짜 약수가 되려면 N이 A의 배수여야하고, A가 1과 N이 아니어야한다고 한다. 그리고 입력으로 진짜 약수가 모두 주어진다.
그렇다면.

진짜 약수가 4 2 일 때 N은 8이다.

진짜 약수가 3 4 2 12 6 8 일 때 N은 24이다.

생각해보자. 진짜 약수들은 모두 N이 배수가 된다. 그렇다면 간단히 생각해서 가장 작은 배수(진짜 약수)와 가장 큰 배수(진짜 약수)를 곱하면 N을 구할 수 있지 않을까?

진짜 약수가 3 4 2 12 6 8 인 경우를 다시 살펴보면 가장 큰 진짜 약수는 12이다. 그 후의 진짜 약수가 없다는 얘기는 12로 나누어 떨어지는 수가 끝이라는 이야기이다. 그래서 가장 작은 진짜 약수 * 가장 큰 진짜 약수 = N이 성립한다.

가장 작은 진짜 약수가 3이어도 이는 성립한다.

N이 21이면 진짜 약수가 3과 7인데, 7 이 후 진짜 약수가 없다는 이야기는 7로 나누어 떨어진다는 이야기이고 이는 가장 작은 배수인 3과 동일하다.

다음은 자바로 작성한 풀이 코드이다.

public class Main{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int[] realPrime = new int[N];

        for( int i = 0; i < N; i++ )
            realPrime[i] = Integer.parseInt(st.nextToken());

		// 정렬
        Arrays.sort(realPrime);
		// 가장 작은 진짜 약수 * 가장 큰 진짜 약수
        System.out.println( N == 1 ? realPrime[0] * realPrime[0] : realPrime[0] * realPrime[realPrime.length-1] );

    }