👀 문제
https://www.acmicpc.net/problem/2609
👊 도전
1. 설계
- 유클리드 호제법을 이용하여 최대공약수를 구한다.
- a, b를 곱한 값을 최대공약수로 나눈 것이 최소공배수이다.
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
29
30
31
32
33
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 input=new Scanner(System.in);
int a=input.nextInt();
int b=input.nextInt();
if(a<b) {
int temp=a;
a=b;
b=temp;
}
int gcd=gcd(a,b);
int lcm=a*b/gcd;
System.out.println(gcd);
System.out.println(lcm);
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 최대공약수를 구한다
- 유클리드 호제법을 이용한다. a>b일때 a%b==0이면 b가 최대공약수, 아니라면 a=b, b=r(a%b)로 다시 최대공약수를 구하는 방법이다.
- gcd메소드를 생성하여 파라미터 a, b를 이용하여 구한 나머지가 0이 될 때까지 반복한다.
- 최소공배수를 구한다
- a, b의 곱에서 최대공약수를 나눈 값이 최소공배수이다.