[java] 1037. 약수

문제

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

입력

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

출력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

---

최소공배수를 찾는 문제였다. 처음에 문제 파악하는데 시간이 좀 걸렸다. 최대 공약수를 찾는 것에만 급급했다. 

 

근데 이게 아니었다. 핳 주어진 약수 중 가장 큰 값과 가장 작은 값을 곱하면 되는 문제 였다. 이유는, 약수가 모두 주어지기 때문.

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));

        // N의 약수 개수
        int numN = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] divisors = new int[numN];

        // N의 약수 입력받기
        for (int i = 0; i < numN; i++) {
            divisors[i] = Integer.parseInt(st.nextToken());
        }

        // 약수들의 최소 공배수 계산
        int result = lcm(divisors);

        // 결과 출력
        System.out.println(result);
    }

    // 최소 공배수 구하기
    public static int lcm(int[] numbers) {
        int result = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            result = lcm(result, numbers[i]);
        }
        return result;
    }

    // 두 수의 최소 공배수 구하기
    public static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    // 유클리드 호제법을 이용한 최대공약수 구하기
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

최소 공배수와 최대 공약수 코드는 좀 외워둬야 할 것 같다. 매번 손으로 쓰고 작성하는 것도 귀찮아지기 시작했다. 얼른 손에 익었으면 좋겠다.

 

그리고 이 코드의 정답은 아래와 같다.

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));

        int T = Integer.parseInt(br.readLine());

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        while(T-- > 0) {
            int N = Integer.parseInt(st.nextToken());
            max = N > max ? N : max;
            min = N < min ? N : min;
        }
        System.out.println(max * min);
    }
}