백준 2702번 초6 수학 (with Java)

https://www.acmicpc.net/problem/2702

2702번: 초6 수학

 

최대공약수, 최소공약수 문제는 "유클리드 알고리즘"을 이용하면 쉽게 풀 수 있다. 

 

 

 

유클리드 알고리즘이란?

유클리드 알고리즘은 주어진 두 수 사이에 존재하는 최대공약수(GCD)를 구하는 알고리즘 이다. 

 

 

 

 

 

유클리드 알고리즘의 원리  

임의의 두 자연수 a, b (a > b) 가 주어졌을 때 a % b == 0 이라면 최대 공약수는 b이다. a % b != 0 이라면 a, a % b로 다시 나누어지는지 확인을 한다. 이러한 과정을 반복문 or 재귀함수를 이용해서 풀 수 있다. 

 

 

 

말보다는 코드를 보면서 이해해보자. 

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이 나오는 것을 확인할 수 있다. 이러원리로 위에서 최소공배수를 구해주면 된다.