최소공배수
문제
두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.
두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)
출력
첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.
예제 입력 1
3
1 45000
6 10
13 17
예제 출력 1
45000
30
221
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 128 MB | 47967 | 27114 | 23152 | 58.093% |
정답 코드는 맨 아래 있습니다.
시간 초과 코드
package Day1005;
import java.util.Scanner;
public class B1934 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
//테스트 케이스 수 만큼 반복
for (int k = 0; k < T; k++) {
int A = sc.nextInt();
int B = sc.nextInt();
int result = 0;
for (int i = B; i > 0; i--) { // i++로 하면 숫자가 작은 순서대로 나와서 출력했을 때 제일 큰 수가 나온다.
for (int j = A; j > 0; j--) {
if (A * i == B * j) {
result = A * i;
}
}
}
System.out.println(result);
}
sc.close();
}
}
아..슬프다 시간 초과라니
답은 잘 나왔는데ㅠㅠ
찾아보니 이 문제는 이렇게 풀라고 출제 된 것이 아니라
유클리드 알고리즘으로 풀라고 나온 문제다
.즉, **유클리드 호제법(**Euclidean algorithm)을 사용하라는 것
아니 저게 뭐야....어려운 문제 아니야..? 싶을 수 있지만 진짜 진짜 쉽다.
유클리드 호제법을 이용해서 최대공약수를 구한 후,
두 수의 곱을 최대공약수로 나누면 최소공배수를 구할 수 있다.
호제법이란? 두 수가 서로 상대수를 나누어서 결국 원하는 수를 얻는 알고리즘
예시를 하나 들겠다.
1071과 1029의**최대 공약수(GCD)**를 구하면,
- 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
- 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
- 42는 21로 나누어 떨어진다.
따라서, 최대공약수는 21이다.
78696과 19332의**최대 공약수(GCD)**를 구하면,
78696 ＝19332×4 ＋ 1368
19332 ＝ 1368×14 ＋ 180
1368 ＝ 180×7 ＋ 108
180 ＝ 108×1 ＋ 72
108 ＝ 72×1 ＋ 36
72 ＝ 36×2 ＋ 0
따라서, **최대 공약수(GCD)**는 36이다.
❤️ 간단하게 말하면, 유클리드 호제법은 MOD연산을 반복하면 된다!
그러나 몇 번의 반복을 통해서 나머지가 0이 되는지 알 수 없으므로
반복문으로 구현하는 것이 아니라 재귀 형태로 구현해야 한다.
/**
* 유클리드 호제법 구현 메서드
* @param bn : 큰 숫자
* @param sn : 작은 숫자
* @return
* 큰 숫자를 작은숫자로 나눈 값이 0이면 작은숫자 리턴, 아니면 재귀형태로 자신을 호출
*/
public int eucd(int bn, int sn) {
// 큰숫자를 작은숫자로 나눈 나머지를 계산
int r = bn % sn;
// 나머지가 0이면 작은숫자가 최대공약수이므로 작은숫자 리턴
if (r == 0) {
return sn;
} else {
// 나머지가 0 이상이면 재귀형태로 호출
// 이때 파라미터는 작은숫자와 나머지를 넣어줌
return eucd(sn, r);
}
}
출처: <https://codingnojam.tistory.com/58> [아는 만큼 재밌는 개발 Coding Knowjam(코딩노잼):티스토리]
자 그럼 위 코드를 참고하여 유클리드 호제법을 이용해서 풀어보자
유클리드 호제법
package Day1007;
import java.util.Scanner;
public class B1934 {
// 최대공약수 구하기 예) 6 10
public static int GCD(int a, int b) {
// 큰숫자를 작은숫자로 나눈 나머지를 계산
int r = a % b;
// 나머지가 0이면 작은 숫자가 최대 공약수 이므로 작은 숫자를 리턴한다.
// 예) 4 2 -> 4를 2로 나누면 나머지가 0이다. 즉 2는 최대 공약수가 된다.
if (r == 0) {
return b;
// 만약 나머지가 0이 아니라면 b가 a자리로 가고, a를 b로 나눈 나머지가 b의 자리로 간다.
// 예) 6 10 -> GCD(10, 6) -> GCD(6, 4) -> GCD(4, 2)
// 이제 4에서 2를 나누면 나머지가 0이 되므로 2가 최대공약수가 된다.
} else {
return GCD(b, a % b);
}
}
// 최소공배수 구하기
public static int LCM(int a, int b) {
// 최소공배수는 두 수를 곱하고 최대 공약수로 나눈다.
// 예) 6 10 -> 6 * 10 / 2 .... 즉 30이 최소공배수
return a * b / GCD(a, b);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
//두 수 입력받고 테스트 케이스 만큼 반복
for (int i = 0; i < T; i++) {
int A = sc.nextInt();
int B = sc.nextInt();
System.out.println(LCM(A, B)); //최소공배수
}
sc.close();
}
}