[BaekJoon] 2824 최대공약수

1.  문제 링크

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

2.  문제

요약

• N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 되는데, 두 정수 A, B의 최대공약수를 계산하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1000보다 작거나 같은 N이 주어지고 두 번째 줄에 1,000,000,000보다 작거나 같은 양의 정수 N개가 주어지며 세 번째 줄에 1보다 크거나 같고 1000보다 작거나 같은 M이 주어지고 네 번째 줄에 1,000,000,000보다 작거나 같은 양의 정수 M개가 주어집니다.
  • 두 번째 줄의 N개의 정수를 곱하면 A, 네 번째 줄의 M개의 정수를 곱하면 B가 됩니다.
• 출력: 첫 번째 줄에 A, B의 최대공약수를 출력합니다. 만약 9자리보다 길다면, 마지막 9자리만 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.ArrayList;

public class Main {
	public BigInteger gcd(BigInteger max, BigInteger min) {
		if(min.compareTo(BigInteger.ZERO) == 0) {
			return max;
		}
		return gcd(min, max.mod(min));
	}
	
	public String getGCD(String[] first_num, String[] second_num) {
		BigInteger first = BigInteger.ONE;
		for(int i = 0; i < first_num.length; i++) {
			first = first.multiply(new BigInteger(first_num[i]));
		}
		BigInteger second = BigInteger.ONE;
		for(int i = 0; i < second_num.length; i++) {
			second = second.multiply(new BigInteger(second_num[i]));
		}
		BigInteger max = first.compareTo(second) > 0 ? first: second;
		BigInteger min = first.compareTo(second) > 0 ? second: first;
		BigInteger gcd_num = gcd(max, min);
		String gcd_str = gcd_num.toString();
		if(gcd_str.length() <= 9) {
			return gcd_str;
		} else {
			return gcd_str.substring(gcd_str.length() - 9, gcd_str.length());
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		String[] first_num = new String[num];
		String[] input = br.readLine().split(" ");
		for(int i = 0; i < num; i++) {
			first_num[i] = input[i];
		}
		num = Integer.parseInt(br.readLine());
		String[] second_num = new String[num];
		input = br.readLine().split(" ");
		for(int i = 0; i < num; i++) {
			second_num[i] = input[i];
		}
		br.close();
		Main m = new Main();
		bw.write(m.getGCD(first_num, second_num) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 주어진 N개의 정수와 M개의 정수를 이용하여 A, B를 구한 후에 유클리드 호제법을 이용하여 A, B의 최대공약수를 구합니다.
• A, B를 구할 때, 정수의 개수는 최대 1000개이고 각 정수의 최댓값이 1,000,000,000이기 때문에 A와 B의 최댓값이 $1,000,000,000^{1000}$이 됩니다.
• 이 수는 일반적인 정수형으로는 표현할 수 없기 때문에 BigInteger를 이용하여 A, B를 구하고 A, B의 최대공약수를 구합니다.

1. 주어진 N개의 수들과 M개의 수들을 각각 first_num, second_num 배열에 넣습니다.
2. first_num들을 모두 곱해주며 A를 구하고 이 때 A의 자료형은 BigInteger로 설정합니다.
3. second_num들을 모두 곱해주며 B를 구하고 이 때 B의 자료형은 BigInteger로 설정합니다.
4. A와 B 두 수 중에서 더 큰 값을 max에, 더 작은 값을 min에 설정해줍니다.
5. 유클리드 호제법을 이용하여 A, B의 최대공약수를 구하고 해당 값을 gcd_num에 넣어줍니다.
6. gcd_num의 값을 String 자료형으로 변경하고 이를 변수 gcd_str에 넣어줍니다.
7. 만약 gcd_str의 길이가 9보다 작거나 같다면 해당 값을 그대로 출력하고 그렇지 않다면 뒤의 9자리를 출력해줍니다.