[백준] 1934번 - GCD(최대공약수)와 LCM(최소공배수). 유클리드 호제법

두 자연수 A와 B가 주어졌을 때, 최소공배수를 묻는 문제이다.
최소공배수를 구하는 방법은 공식화가 되어있다.

먼저, 다음 용어들을 알아 둘 필요가 있다.

• GCD (Greatest Common Divisor) : 최대공약수

  • 공통 약수 중 최댓값

• LCM (Least Common Multiple) : 최소공배수

  • 공통 배수 중 최솟값

• 유클리드 호제법 : 두 수의 최대공약수(GCD)를 구할 때, 큰 수를 작은 수로 나눈 나머지를 계속 이용해서 반복하는 알고리즘

---

최대 공약수 GCD를 구하는 유클리드 호제법 알고리즘은 다음과 같다.

public static int gcd(int a, int b){
	while(b != 0){
    	int tmp = a % b;
        a = b;
        b = tmp;
}

유클리드 호제법은 큰 수를 작은 수로 나눈 나머지를 계속 이용한다.

1. 편의상 큰 수는 a에, 작은 수는 b에 놓고 연산한다.
2. tmp에 두 수를 나눈 나머지가 저장되고, 작은 수를 넣는 쪽인 b에 저장한다.
3. 위 과정을 반복한다.

비로소 나머지가 0이 나오면, 마지막에 a에 저장된 수가 최대공약수가 된다.

---

그리고 최소공배수 LCM은 다음과 같은 공식을 사용할 수 있다.

즉 정리하자면,
문제에서 요구하는 최소공배수(LCM)은 유클리드 호제법 알고리즘을 사용해 최대 공약수(GCD)를 구한 다음, 공식을 사용해서 구할 수 있다.

위 정보를 바탕으로 설계한 코드는 다음과 같다.

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

class Main{
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine());
        for(int i=0; i<T; i++){
        	st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int result = lcm(a, b);
            bw.write(result + "\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }
    
    static int lcm(int a, int b){
    	return a * b / gcd(a, b);
    }
    
    static int gcd(int a, int b){
    	while(b != 0){
        	int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }
}

맞았습니다!!