백준 2702번 초6 수학 (with Java)
https://www.acmicpc.net/problem/2702
2702번: 초6 수학
문제 두 정수 a와 b 최소공배수는 두 수의 공통된 배수 중 가장 작은 수이고, 최대공약수는 두 수의 공통된 약수중 가장 큰 수이다. a와 b가 주어졌을 때, 최소공배수와 최대공약수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 각 테스트 케이스는 두 정수 a와 b로 이루어져 있고, 공백으로 구분되어 있다. (1 <= a,b <= 1,000) 출력 각 테스트 케이스에 대해 최소공배수와 최대공약
www.acmicpc.net
최대공약수, 최소공약수 문제는 "유클리드 알고리즘"을 이용하면 쉽게 풀 수 있다.
유클리드 알고리즘이란?
유클리드 알고리즘은 주어진 두 수 사이에 존재하는 최대공약수(GCD)를 구하는 알고리즘 이다.
유클리드 알고리즘의 원리
임의의 두 자연수 a, b (a > b) 가 주어졌을 때 a % b == 0 이라면 최대 공약수는 b이다. a % b != 0 이라면 a, a % b로 다시 나누어지는지 확인을 한다. 이러한 과정을 반복문 or 재귀함수를 이용해서 풀 수 있다.
말보다는 코드를 보면서 이해해보자.
|
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
|
import java.util.Scanner;
public class Main_2702 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
for (int i = 0; i < n; ++i) {
int a = input.nextInt();
int b = input.nextInt();
int k = GCD(a, b);
System.out.print(a * b / k + " ");
System.out.println(k);
}
}
public static int GCD(int a, int b) {
if (a % b == 0) {
return b;
}
return GCD(b, a % b);
}
}
|
GCD 메소드를 확인해보면 매게변수로 a, b를 받고 a % b == 0 이라면 b가 최대공약수가 되므로 return b를 한다.
a % b != 0 이라면 b, a % b를 매게변수로 넘겨 재귀함수를 이용한다.
예를들어,
a = 42, b = 56 이라고 하자. 42 % 56 != 0 이므로 (56, 14) 를 매게변수로 넘겨준다. 56 % 14 == 0 이므로 최대공약수는 14가 된다.
그렇다면 최소공배수는 어떻게 구하는 것일까?
예를들어
12 = 2 * 2 * 3
20 = 2 * 2 * 5
가 있다고 가정하자. 최대공약수는 2 * 2 = 4(공통된 부분)이고, 최소공배수는 중복을 제외하고 2 * 2 * 3 * 5 = 60이다.
따라서 (12 * 20 / 최대공약수)를 해주면 최소공배수를 구할 수 있다. 12 * 20 / 4 를 하면 60이 나오는 것을 확인할 수 있다. 이러원리로 위에서 최소공배수를 구해주면 된다.