[Baekjoon] 9770_GCD

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

---

< GCD >

 

문제 풀이 

 

모든 쌍에 대하여 최대공약수를 구해 최댓값을 구한다.

 

my solution (Java)

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

public class _9770_ { // GCD

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

		String str = "";
		int result = 0;

		ArrayList<Integer> list = new ArrayList<>();
		while ((str = bf.readLine()) != null) {
			st = new StringTokenizer(str);

			while (st.hasMoreTokens()) {
				list.add(Integer.parseInt(st.nextToken()));
			}
		}
		for (int i = 0; i < list.size() - 1; i++) {
			for (int j = i + 1; j < list.size(); j++) {
				result = Math.max(result, gcd(list.get(i), list.get(j)));
			}
		}
		System.out.println(result);
	}

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

변수)
str : 입력값
result : 최대공약수의 최댓값
list : ArrayList <Integer> 

 

입력값이 없을 때까지 입력받아 ArrayList에 저장한다. ArrayList를 이중 for문을 사용하여 구할 수 있는 모든 쌍을 구해 최대공약수를 구한다. 구한 최대공약수 중에서 최댓값을 구해 출력한다.

---

---