[Java] 백준 15단계 - 1934번 문제 (최소공배수)

문제설명

 

소스코드

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		for(int i = 0; i < T; i++) {
			int a = in.nextInt();
			int b = in.nextInt();
			System.out.println(a * b / gcd(a, b));
		}
	}
	public static int gcd(int a, int b)
	{
	    if(b == 0) return a;
	    else return gcd(b, a % b);
	}
}

 

설명

• 최소공배수와 최대공약수와의 관계는 아래와 같다.
  두 자연수의 곱 = 최대공약수 × 최소공배수
  최소공배수 = 두 자연수의 곱 / 최대공약수
• 유클리드 호제법으로 최대공약수를 구한다(재귀 이용)

유클리드 호제법
위 알고리즘은 유클리드 호제법을 이용한 것이다.
두 정수를 직사각형의 두 변의 길이라고 생각하면 두 정수의 최대공약수를 구하는 문제는
직사각형을 정사각형으로 완전히 채우고 이렇게 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하면 된다.

1.짧은 변의 길이를 한 번으로 하는 정사각형으로 채운다.
2.남은 직사각형에 대해 같은 작업을 반복
3.정사각형만으로 구성되었을 때의 변의길이가 최대공약수