백준 2824. 최대공약수

🅰 백준 2824. 최대공약수

2824번: 최대공약수

✏️ 문제 풀이

• 이 문제는 아래처럼 조건이 매우 까다롭다.

• 첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다. 셋째 줄에 M(1 ≤ M ≤ 1000)이 주어진다. 넷째 줄에는 M개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, M개의 수를 곱하면 B가 된다.

• 하지만 최대공약수, 큰 수 2개의 키워드를 보고 유클리드호재, BigInteger를 사용하면 되겠다 라는 생각이 바로 들었다. 
• 유클리드 호재에 대해 궁금하다면 ?

CT(수의 표현, 유클리드 호제, 페르마의 소정리)

• BigInteger에 대해 궁금하다면 ?

[BigInteger] 무한대로 큰 수를 계산해야 한다면? BigInteger

• 위에 두 글을 참고하면 되겠다. 그럼 두 개념을 다 이해한다 생각하고 설명을 하겠다.
• 일단 주어지는 수를 계속 곱해줘야 하기 때문에 A와 B를 1로 초기화 해서 선언해줬다.
• BigInteger의 메소드를 이용하여 A와 B의 값을 곱해서 구해주었다.
• A와 B를 준비한 뒤 최대공약수를 구하기 위해 매우 큰 수일때 최대공약수를 구하는 방법인 유클리드 호재 방식을 이용하여 A와 B의 크기를 compareTo() 메소드를 이용하여 비교해주었고,
• 유클리드 호재의 종료조건으로 A나 B가 0이되면 0이 아닌 수가 최대공약수가 되므로 StringBuilder에 저장해주었다. StringBuilder에 넣은 이유는 아래에서 설명하겠다.
• 만약 A가 더 크면 B값을 temp에 넣어주고, B %= A; 를 한 다음 A=temp를 해주었다. (유클리드 호재의 계산 방식)
• B가 더 크면 반대로 해주었다.
• while문을 통해 무한으로 반복하다가, 종료조건에 부합하면 while문을 빠져나온다.
• 종료조건을 충족시켰을 때 바로 종료하지 않고 StringBuilder를 이용해서 저장해 온 이유는 문제의 조건에서

  만약, 9자리보다 길다면, 마지막 9자리만 출력한다. (최대 공약수가 1000012028인 경우에는 000012028을 출력해야 한다)

  라는 조건이 있었기 때문이다.
• 그러므로 최대공약수가 9자리보다 더 크면 StringBuilder의 substring메소드를 이용하여 마지막 기준으로 9번째 자리부터 마지막까지의 수를 출력하였고, 9자리보다 작으면 sb값을 바로 출력해주었다.

✏️ 소스코드

spackage codingtestPractice.골드_골드5_최대공약수;

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

public class Main_2824 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		BigInteger A = new BigInteger("1");
		BigInteger B = new BigInteger("1");
		BigInteger zero = new BigInteger("0"); // 유클리드 호제를 위한 0
		BigInteger temp = new BigInteger("1"); // 유클리드 호제를 위한 0
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			BigInteger mul = new BigInteger(st.nextToken());
			A = A.multiply(mul);
		}
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			B = B.multiply(new BigInteger(st.nextToken()));
		}
		while (true) {
			if (A.compareTo(zero) <= 0) {
				sb.append(B.toString());
				break;
			} else if (B.compareTo(zero) <= 0) {
				sb.append(A.toString());
				break;
			}
			boolean compare = A.compareTo(B) == 1 ? true : false; // 만약 A>B이면
			if (compare) { // 만약 A가 B보다 크면
				temp = B;
				B = A.remainder(B);
				A = temp;
				
			} else { // 만약 B보다 A가 크면
				temp = A;
				A = B.remainder(A);
				B = temp;
			}
		}
		if(sb.length()>9)
		System.out.println(sb.substring(sb.length()-9, sb.length()));
		else
			System.out.println(sb);
	}
}

 

✅ 후기

• 정답률이 22%밖에 안되서 어려운문제라 생각했는데 문제를 보자마자 여태껏 공부했던 개념들이 하나씩 떠오르면서 이런식으로 접근하면 되겠구나! 라는 생각이 바로 떠올랐고, 그렇게 문제를 풀었을 때 맞아서 기분이 좋았다.
• 역시 많은것을 알면 알수록 문제를 보는 시야갸 넓어진다는 것을 요즘에서야 깨닫고 있다.