-
백준 2609 - 최대공약수와 최소공배수(JAVA)Algorithm 2022. 10. 2. 14:53728x90
2609번: 최대공약수와 최소공배수 (acmicpc.net)
문제는 엄청나게 쉽다. 그냥 두 개의 숫자를 입력받고 그 숫자들의 최대공약수와 최소공배수를 구하면 된다.
최대공약수를 구하는 알고리즘을 유클리드 호제법이 쉽다는 것을 알고 있으면 정말 순식간에 문제를 해결 할 수 있게 된다.
※ 최대공약수 알고리즘
- 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함수를 나누어 깔끔하게 문제를 해결할 수 있었다.
728x90'Algorithm' 카테고리의 다른 글
백준 2163 - 초콜릿 자르기(JAVA) (1) 2022.10.05 백준 9506 - 약수들의 합(JAVA) (1) 2022.10.03 백준 2563 - 색종이(JAVA) (0) 2022.10.02 백준 2775 - 부녀회장이 될테야(JAVA) (0) 2022.09.28 백준 10769 - 행복한지 슬픈지(JAVA) (0) 2022.09.28