[백준] 1934 : 최소공배수 - JAVA

🙋🏻‍♀️ 유클리드 호제법 이용

문제분석

a,b의 최소공배수는 a*b/최대공약수로 구할 수 있다.
따라서 유클리드 호제법을 이용해 최대공약수를 구한후 진행하면된다.

A,B의 최대값은 45,000이므로 유클리드 호제법을 이용하면 한 번에 O(log45,000)이고, 이것을 T번 반복하는데 T의 최대는 1,000이므로, O(1000*log45,000) = O(15000)이다
따라서 제한시간 1초안에 가능하다.

슈도코드

T입력받기
for(T번 반복) {
	a,b입력받기
    euclid(a,b) 출력 
}

euclid(int a,b) {
	if(a<b) {
    	swap연산 수행
    }
	int result = a%b;
    if(result == 0) return b
    euclid(b,result);
}

제출코드

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

public class Main {
static int gcd;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int i=0; i<T; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			euclid(a,b);
			int answer= 0 ;
			answer = (a*b)/gcd;
		    System.out.println(answer);
		}

	}
	public static void euclid(int a, int b) {
		if(a<b) {
	    	int temp = a;
	    	a = b;
	    	b = temp;
	    }
		int result = a%b;
	    if(result == 0) gcd = b;
	    else euclid(b,result);
	}
}