[Baekjoon] 9417_최대 GCD

Silver IV

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

---

< 최대 GCD >

 

문제 풀이 

 

모든 두 수의 최대공약수를 찾아 최댓값을 찾는다.

 

 

 my solution (Java)

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

public class _9417_ { // 최대 GCD

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

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

		ArrayList<Integer> list = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());

			while (st.hasMoreTokens()) {
				list.add(Integer.parseInt(st.nextToken()));
			}

			int max = 0;
			for (int j = 0; j < list.size(); j++) {
				for (int k = j + 1; k < list.size(); k++) {
					int num = gcd(list.get(j), list.get(k));
					max = Math.max(num, max);
				}
			}
			bw.write(max + "\n");
			list.clear();
		}
		bw.flush();
	}

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

변수)
m : 테스트 케이스의 개수
list : 입력으로 주어진 수
max : 가장 큰 최대공약수

 

테스트 케이스의 개수를 입력받는다. 테스트 케이스의 수만큼 다음 과정을 반복한다.

 

1) 입력으로 주어진 수를 ArrayList에 저장한다.

2) 모든 두 수의 쌍을 gcd함수를 통해 최대 공약수를 구한다.

3) 최대 공약수의 최댓값을 구한다.

4) 가장 큰 최대공약수를 출력한다.

 

gcd(Integer a, Integer b)

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

2) gcd(b, a% b)를 호출한다.

---

---