백준 - 최대공약수(2824)

문제 출처

문제 출처 : 최대공약수

문제 이해하기

두 양의 정수 A와 B의 최대공약수를 계산하는 문제이다.

주요 조건 이해하기 ⭐️

A와 B의 최대공약수를 구하는 문제이다. 하지만 순수히 A와 B의 값을 바로 알려주는 문제는 아니다

N개의 수와 M개의 수가 주어졌을 때, N개의 수를 곱하면 A가 되고 M개의 수를 곱하면 B가 된다.

쉽게 설명하면 N의 입력값으로 3이 들어오면 3개의 숫자가 들어오고 이 3개의 숫자를 곱해야 A가 된다는 이야기다.

N = 3
(2, 3, 5) 총 3개의 숫자가 들어오고 이를 곱하면 30이 되고 A는 30이라는 뜻이다.

M도 마찬가지다
M = 2
(4, 5) 총 2개의 숫자가 들어오고 이를 곱하면 20이 되고 B는 20이라는 뜻이다.

이제부터 최대공약수만 구하면 끝나는 문제이다.
하지만 문제에서 매우 큰 A와 B를 주었기 때문에 BigInteger 클래스를 사용해서 문제를 풀었다. 어떻게 풀지 순서를 정리해보면

1. 입력을 받는다.
2. N개의 수를 곱한 후 A를 구한다.
3. M개의 수를 곱한 후 B를 구한다.
4. A, B의 최대공약수를 구한다.
5. 결과값이 9자리를 초과할 경우 (분기)
   5-1. 마지막 9자리까지 출력
   5-2. 그대로 출력

이 순서로 코드를 작성하였고, 참고로 BigInteger 클래스에서 최대공약수를 구하는 메소드가 있기 때문에 별도의 최대공약수를 구하는 메소드를 만들지 않고 그대로 호출하여 문제를 해결했다.

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class _2824_ {

	static int N, M;
	static BigInteger[] n, m;
	static final int MAX_LENGTH = 9;


	// N, M을 입력받고 N, M개의 대한 데이터를 받기 위해 n,m 배열로 선언
	private static void init() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		n = new BigInteger[N];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			n[i] = new BigInteger(st.nextToken());
		}

		M = Integer.parseInt(br.readLine());
		m = new BigInteger[M];

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < M; i++) {
			m[i] = new BigInteger(st.nextToken());
		}
	}

	private static BigInteger gcd(BigInteger a, BigInteger b) {
		BigInteger max = a.max(b);
		BigInteger min = a.min(b);

		return max.gcd(min);
	}

	// A, B 각각 최대 공약수를 구한다.
	private static String calculateGCD() {
		BigInteger result1 = BigInteger.ONE;
		BigInteger result2 = BigInteger.ONE;

		// N개의 수를 곱한다.
		for (int i = 0; i < N; i++) {
			result1 = result1.multiply(n[i]);
		}

		for (int i = 0; i < M; i++) {
			result2 = result2.multiply(m[i]);
		}

		return gcd(result1, result2).toString();
	}

	public static void main(String[] args) throws IOException {

		init();
		String result = calculateGCD();

		// 길이가 9를 넘는 경우 그 만큼 빼준다.
		if (result.length() > MAX_LENGTH) {
			result = result.substring(result.length() - MAX_LENGTH);
		}

		System.out.println(result);
	}
}

참고자료

BigInteger 클래스 정리