코딩 테스트 [정수론] - 최소 공배수 구하기

두 자연수 A와 B가 있을 때 A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중 가장 작은 수를 최소 공배수라고 한다. 예를 들어 6과 15의 공배수는 30, 60, 90 등이 있으며, 최소 공배수는 30이다. 두 자연수 A와 B가 주어졌을 때 A와 B의 최소 공배수를 구하는 프로그램을 작성하시오.

(시간 제한 1초)

---

입력

1번째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000), 2번째 줄부터 T개의 줄에 걸쳐 A와 B가 주어진다(1 ≤ A, B ≤ 45,000).

출력

1번째 줄부터 T개의 줄에 A와 B의 최소 공배수를 입력받은 순서대로 1줄애 1개씩 출력한다.

예제 입력
3	// 테스트 케이스의 개수
1 45000	// A, B
6 10
13 17

예제 출력
45000
30
221

---

1단계 - 문제 분석하기

최소 공배수는 A와 B가 주어졌을 때 'A * B / 최대 공약수'를 계산해 구할 수 있습니다. 결국 이 문제는 유클리드 호제법을 이용해 최대 공약수를 구한 후 두 수의 곱에서 최대 공약수를 나눠 주는 것으로 해결할 수 있다.

2단계 - 손으로 풀어 보기

1 유클리드 호제법을 이용해 A와 B의 최대 공약수를 구한다.

2 두 수의 곱을 최대 공약수로 나눈 값을 정답으로 출력한다.

※ 최대 공약수가 2이므로 최소 공배수는 6 * 10 / 2 = 30

3단계 - sudo코드 작성하기

t(테스트 케이스)

for(t만큼 반복하기)
{
	a(1번째 수) b(2번째 수)
    결괏값 = a * b / gcd(a, b)
    결괏값 출력하기.
}

gcd(int a, int b)
{
	if(b가 0이면)
    	a가 최대공약수
    else
    	gcd(작은 수, 큰 수 % 작은 수)
}

4단계 - 코드 구현하기

import java.util.Scanner;

public class Q42 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int i = 0; i < t; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int result = a * b / gcd(a, b);
            System.out.println(result);
        }
    }

    public static int gcd(int a, int b){
        if(b == 0)
            return a;
        else
            return gcd(b, a % b);
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편