백준 2609 - 최대공약수와 최소공배수(JAVA)

2609번: 최대공약수와 최소공배수 (acmicpc.net)

2609번: 최대공약수와 최소공배수

 

문제는 엄청나게 쉽다. 그냥 두 개의 숫자를 입력받고 그 숫자들의 최대공약수와 최소공배수를 구하면 된다.

 

최대공약수를 구하는 알고리즘을 유클리드 호제법이 쉽다는 것을 알고 있으면 정말 순식간에 문제를 해결 할 수 있게 된다.

 

※ 최대공약수 알고리즘

- GCD 재귀로 구현

- G(a, b) = G(b, r) (단, r = amodb) -> 유클리드 호제법

- b가 0일 때 나눌 수 없으므로 미리 b가 0이면 a로 출력시켜 줄 수 있도록 처리해주어야 Arithmetic error가 나오지 않는다.

 

※ 최소공배수 알고리즘

- 처음 생각한 알고리즘 : a와 b를 입력받았으니, "a * b * 최대공약수" 이렇게 하면 끝날 줄 알았음

- but, 입력 예시를 통해 알고리즘을 생각해보자. 24 18 -> 24 = 2 * 12, 18 = 2 * 9 => 최대공약수: 2, 최소공배수: 2 * 12 * 9

- a와 b를 입력 받았으면 "(a * b) / 최대공약수" 로 알고리즘 처리 완료

 

 

이렇게 최대공약수 GCD함수, 최소공배수 MCM함수를 나누어 깔끔하게 문제를 해결할 수 있었다.