[JAVA] 백준 2609번 : 최대공약수와 최소공배수

https://www.acmicpc.net/problem/2609
최대공약수와 최소공배수의 개념을 알고 있어야 풀 수 있는 문제이다.
최대공약수 : 숫자가 가장 큰 공약수
최소공배수 : 숫자가 가장 작은 공배수

이 때, 최대공약수는 유클리드 호제법을 이용하여 구할 수 있으며, 최소공배수는 두 수를 곱한 후 최대공약수로 나누어 구할 수 있다.

유클리드 호제법

두 수 A, B가 있을 때
1. A를 B로 나눈 나머지를 구한다
2. 이 나머지를 R이라고 한다
3. A를 B로, B를 R로 바꿔서 반복한다
4. 나머지가 0이 될 때 까지 반복한다
5. 나머지가 0이 되었을 때의 B가 최대공약수이다

ex)56과 42
1. 56을 42로 나눈 나머지 R -> 14
2. 42를 14로 나눈 나머지 R -> 0
3. 14가 두 수의 최대공약수

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int a = Integer.parseInt(input[0]);
        int b = Integer.parseInt(input[1]);

        int GCD = gcd(a, b); //최대공약수 : 두 수의 나머지를 나눈 수에 나눴을 때 0이 되는 것. 유클리드 호제법
        int LCM = (a * b) / GCD; //최소공배수 : 두 수를 곱했을 때 최대공약수로 나누게 된 수
        System.out.println(GCD);
        System.out.println(LCM);
        br.close();
    }

    public static int gcd(int a, int b) {
        while(b != 0){
            int r = a % b;
            a = b;
            b = r;
        }
        return a; //b를 a라는 이름으로 return
    }
}