[Baekjoon] 2824_최대공약수

Silver I

문제(출처: https://www.acmicpc.net/problem/2824)

---

< 최대공약수 >

 

문제 풀이 

 

모든 쌍을 만들어 최대공약수를 구한다.

 

 my solution (Java)

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

public class _2824_ { // 최대공약수

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		st = new StringTokenizer(bf.readLine());
		int narr[] = new int[n];
		for (int i = 0; i < n; i++) {
			narr[i] = Integer.parseInt(st.nextToken());
		}

		int m = Integer.parseInt(bf.readLine());

		st = new StringTokenizer(bf.readLine());
		int marr[] = new int[m];
		for (int i = 0; i < m; i++) {
			marr[i] = Integer.parseInt(st.nextToken());
		}

		long result = 1;
		boolean flag = false;
		for (int i = 0; i < n; i++) {
			if (narr[i] == 1) {
				continue;
			}
			for (int j = 0; j < m; j++) {
				if (marr[j] == 1 || narr[i] == 1) {
					continue;
				}
				int num = gcd(narr[i], marr[j]);
				result *= num;

				if (result >= 1000000000) {
					flag = true;
					result %= 1000000000;
				}

				narr[i] /= num;
				marr[j] /= num;
			}
		}

		String answer = Long.toString(result);
		if (flag) {
			for (int i = 0; i < 9 - answer.length(); i++) {
				System.out.print("0");
			}
		}
		System.out.println(answer);
	}

	private static int gcd(int a, int b) {
		if (b == 0)
			return a;
		else
			return gcd(b, a % b);
	}
}

변수)
n : A의 약수 개수
narr : A의 약수
m : B의 약수 개수
marr : B의 약수
result, answer : 최대공약수
flag : 1000000000으로 나눈 여부

 

A와 B의 약수 개수와 각 약수를 입력받아 값을 저장한다. 이중 for문을 사용하여 가능한 모든 쌍 조합을 만들어 gcd 함수를 호출한다. 이때 값이 1이라면 gcd 함수를 호출하지 않고 다음 쌍으로 넘어간다. gcd 함수를 통해 얻은 최대공약수를 result에 곱하고 각 값에는 나눈다. 이때 result가 1000000000 이상이라면 오버플로우를 방지하기 위해 나누고 flag를 true로 저장한다. 

 

flag가 true라면 1000000000으로 나눈 적이 있으므로 9자리 이상이라는 뜻이다. 그러므로 앞에 빈 자릿수만큼 0으로 채운다. 마지막으로 answer를 출력한다.

 

gcd (int a, int b)

b가 0이라면 a를 반환한다.

b가 0이 아니라면 gcd(b, a% b)를 호출한다.

---

오버플로우 방지를 위해 result 값이 1000000000 이상일 때 나눠줘야 한다는 것을 알아차리지 못했다 😢

---