[백준, JAVA] 2609번 : 최대공약수

seunguk noh·2023년 7월 26일

algorithm

Algorithm

목록 보기

8/23

1. 문제

주어진 두 수의 최대공약수를 구하는 문제이다.

손으로도 많이 연산을 하는 문제라 단순할 것이라 생각했는데,

유클리드 호제법 개념을 몰라서 시간이 좀 걸렸다.

2. 아이디어

유클리드 호제법을 코드로 구현한다.

2-1 유클리드 호제법이란

1071과 1029의 최대공약수를 구하면,

1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
42는 21로 나누어 떨어진다.
따라서, 최대공약수는 21이다.

78696과 19332의 최대공약수를 구하면,

78696 ＝ 19332×4 ＋ 1368
19332 ＝ 1368×14 ＋ 180
 1368 ＝ 180×7 ＋ 108
  180 ＝ 108×1 ＋ 72
  108 ＝ 72×1 ＋ 36
   72 ＝ 36×2 ＋ 0

따라서, 최대공약수는 36이다.

3. 코드


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

public class BOJ_1_2609 {
	public static void main(String[] args) throws IOException  {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String s = bf.readLine();
		StringTokenizer st = new StringTokenizer(s);
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		System.out.println(min(a,b));
		System.out.println(max(a,b));
	}
	
	public static int min(int a, int b) {
		if(a%b==0) return b;
		return min(b, a%b);
	}
	
	public static int max(int a, int b) {
		int m = min(a,b);
		return m*(a/m)*(b/m);
	}
}