[Java] BOJ 2609 최대공약수와 최소공배수

문제 

문제 링크 https://www.acmicpc.net/problem/2609

• 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
• 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
• 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

아이디어

• 최대공약수와 최소공배수를 숫자를 일일이 사용하여 구할려고 하다가 공식이 있었던 것 같아서 문제풀기 전에 먼저 찾아봤었다.
• 그 방법은 유클리드 호제법인데 유클리드 호제법이란 a를 b로 나눈 나머지 r로 b를 나눴을때 나온 나머지 r'이 0이면 그 r이 최대공약수라는 것이다. 만약 0으로 떨어지지 않는다면 a 자리에 b를 넣고 b자리에 r을 넣고 위에 방법을 반복하여 0이 될때까지 최대공약수를 구하면 된다. 
• 최소공배수는 나온 최대공약수를 활용하여 '(a * b) / 최대공약수' 이 식을 사용하면 된다.  

겪은 시행착오

• 유클리드 호제법이 정확히 생각이 나지 않아서 이론을 찾아보면서 공부했던 것 같다. (앞으로 최소공배수나 최대공약수를 구해야되는 문제가 나오면 이 방법을 꼭 숙지해서 수월히 풀어야겠다..!)

파이팅!!

코드

import java.io.*;
import java.util.*;

// 유클리드 호제법
// a,b에 대해서 a를 b로 나눈 나머지를 r이라 한다면 a,b의 최대공약수와 b,r의 최대공약수는 같다.
// 따라서 a를 b로 나눈 나머지 r을 구하고, b를 r로 나눈 나머지 r'을 구한다.
// 나머지가 0이 될때 나눈 수가 a,b의 최대공약수가 된다.
// 해당 방법으로 구한 최대공약수를 활용하여 최소 공배수는 (a * b)/최대 공약수 식으로 구할 수 있다.

public class BOJ2609 {

    static int gcd = 0;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 최소공배수와 최대공약수를 구할 두 수
        int N1 = Integer.parseInt(st.nextToken());
        int N2 = Integer.parseInt(st.nextToken());

        GCD(N1, N2);

        // 유클리드 호제법 식을 활용한 최소공배수 구하는 식
        int lcm = (N1 * N2) / gcd;

        System.out.println(gcd);
        System.out.println(lcm);
    }

    // 최대공약수를 구할 함수
    public static void GCD(int n1, int n2){
        // n1이 n2로 나누어 떨어진다면 n2가 두 수의 최대공약수이므로
        // 최대공약수는 n2고 함수 종료
        if(n1 % n2 == 0){
            gcd = n2;
            return;
        }

        // 만약 나누어떨어지지 않는다면 유클리드 호제법을 이용해서 n2와 n1을 n2로 나눈 나머지로
        // 함수를 다시 돌림
        GCD(n2, n1 % n2);
    }
}