[백준 Bronze I] 최대공약수와 최소공배수 (Java)

 

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

public class Main {

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

		StringTokenizer st = new StringTokenizer(br.readLine());
		int num1 = Integer.parseInt(st.nextToken());
		int num2 = Integer.parseInt(st.nextToken());

		int maxNum = gcd(num1, num2); // 최대 공약수

		bw.write(maxNum + "\n");
		bw.write(num1 * num2 / maxNum + "");
		bw.flush();
		bw.close();

	}

	public static int gcd(int num1, int num2) {
		if (num2 == 0)
			return num1;

		return gcd(num2, num1 % num2);
	}

}

 

 

 

---

 

최대공약수와 최소공배수 구하기...

예전에 수학을 열심히 공부할 때는 그냥 손으로 계산해서 막 풀었는데 막상 코드로 구현하자니 아무것도 생각이 안나서 결국 구글링을 통해 다른 사람들의 코드를 참고하게 되었다.

 

최대 공약수를 구하려면 유클리드 호제법을 이용하면 된다.

그런데 사실 그냥 냅다 계산하면서 풀어서 그게 유클리드 호제법인지 뭔지...잘 모르고 풀었던 터라 들어가서 보고 직접 숫자를 대입해보고 나서야 조금 이해를 했다.

 

유클리드 호제법이란,

a와 b의 최대 공약수를 구할 때 계속해서 나누면서 더 이상 나눠지지 않는 나머지가 최대공약수라는 것이다.

 

 저기 예제 1을 참고해서 이야기 해보자. (숫자는 24와 18)

24 와 18을 3으로 나누면 -> 8 과 6이 나온다

8과 6을 2로 나누면 -> 4와 3이 나온다

이때 최대 공약수는 2x3이고, 최소공배수는 2X3X4X3=72이다.

 

따라서,

최소공배수는 두 수의 최대공약수 X 두 수의 나머지들 을 하면 나온다.
n X m을 하면 최대공약수 X 최대공약수 X 두 수의 나머지이므로 n X m / 최대공약수로 구할 수 있다.

이 방법을 사용하는 걸 gcd 함수를 통해 구현하였다.

사실 코드로 구현하는 게 정말 이해가 잘 안갔다....ㅋㅋㅋ 나만 그런가ㅠ

참고해서 코드를 구현하기는 했는데 시간이 좀 오래 걸린 문제이다.