[백준] 2609번 : 최대공약수와 최소공배수
📍 문제
💡 접근
유클리드 호제법으로 문제를 풀었다.
1. 최대공약수 (GCD: Greates Common Divisor)
유클리드 호제법(Euclidean algorithm)
a, b 의 최대공약수 == b와 a%b의 최대공약수
=> GCD(a, b) = GCD(b, a%b)
a%b가 0이 될 경우 해당 b가 최대공약수이다.
ex ) GCD(581, 322) = GCD(322, 259) = GCD(259, 63) = GCD(63, 7) = GCD(7, 0) = 7
-> 마지막에 a%b가 0이 되었기 때문에 24와 18의 GCD는 6이다.
유클리드 호제법으로 최대 공약수를 구하는 방법 2가지
// 최대공약수 반복문 방식
int gcd(int a, int b) {
while(b != 0) {
int r = a % b; // r = a mod b
// GCD(a, b) = GCD(b, r)이므로 변환한다.
a = b;
b = r;
}
return a;
}
// 최대공약수 재귀 방식
int gcd(int a, int b) {
if(b == 0) return a;
// GCD(a, b) = GCD(b, r)이므로 (r = a % b)
return gcd(b, a % b);
}
2. 최소공배수 (LCM: Least Common Multiple)
최소공배수는 유클리드 호제법을 이용해 구한 최대공약수를 이용해 쉽게 구할 수 있다.
수학적으로 최대공약수와 최대공배수의 곱은 두 수의 곱과 같다.
최대공약수 x 최소 공배수 = 두수의 곱
=> LCM(a,b) = (a * b) / GCD(a, b)
// 최소공배수
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
👩💻 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int d = gcd(a, b);
System.out.println(d); // 최대공약수
System.out.println(a * b / d); // 최소공배수
}
public static int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
}
🔗 링크
https://www.acmicpc.net/problem/2609
참고 : https://st-lab.tistory.com/154
Author And Source
이 문제에 관하여([백준] 2609번 : 최대공약수와 최소공배수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dkfma3323/백준-2609번-최대공약수와-최소공배수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)