👀 문제
https://www.acmicpc.net/problem/1934
👊 도전
1. 설계
- GCD, LCM을 구한다
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Scanner;
/**
* @author HEESOO
*
*/
public class Main {
public static int gcd(int a, int b) {
if(a%b==0) return b;
else return gcd(b, a%b);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int t=scan.nextInt();
for(int i=0;i<t;i++) {
int a=scan.nextInt();
int b=scan.nextInt();
int gcd=a>b? gcd(a,b):gcd(b,a);
int lcm=a*b/gcd;
System.out.println(lcm);
}
}
}
3. 결과
🤟 성공 🤟
4. 설명
- GCD를 구한다
- 최대공약수는 a>b일 때, a%b=r을 계산하여 r=0이면 b가 최대공약수가 되고, 0이 아니라면 b%r을 다시 계산한다.
- 재귀를 통해 r=0이 될 때까지 반복한다.
- LCM를 구한다
- 최소공배수는 a*b/gcd로 구할 수 있다.