문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

입력 📨

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

출력 📩

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

예제 입력

3
1 45000
6 10
13 17

예제 출력

45000
30
221

알고리즘 분류

• 수학
• 정수론
• 유클리드 호제법

문제 해결 ✔️

package PythonSeries1;
/*
 *  백준 문제 1934 : 최소공배수
 *  Site : https://www.acmicpc.net/problem/1934
 */
import java.util.*;

public class Solution_1934 {
    static void lcm(String str) {
        String[] numArr = str.split(" ");
        int lcdNum0 = Integer.parseInt(numArr[0]);
        int lcdNum1 = Integer.parseInt(numArr[1]);
        int maxNum = (lcdNum0 > lcdNum1) ? lcdNum0 : lcdNum1; // 최대 값 구하기
        int lcm = 0;
        for(int i = 1; i <= maxNum; i++) {
                if(lcdNum0 % i == 0 && lcdNum1 % i == 0) {
                        int gcd = i; // 두 수의 최대공배수
                        lcm = lcdNum0 * lcdNum1 / gcd;
                    }
                }

            System.out.println(lcm);
        }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int testNum = sc.nextInt();
        sc.nextLine();

        for(int i = 0; i < testNum; i++) {
            String input = sc.nextLine();
            lcm(input);
        }
        sc.close();
    }
}

해석 🔎

최소공배수의 공식

먼저 최소공배수를 구하는 공식이 무엇일까 ? A * B / 최대공약수 이다.
최소공배수를 구하는 공식을 알았으니 남은 것은 최대공약수를 알아내는 것이다.

최대공약수?

💡 : 약수(common divisor)란 두 수 이상의 여러 수의 공통된 약수를 의미합니다. 최대공약수(GCD)란 두 수 이상의 여러 수의 공약수 중 최대인 수를 가리킵니다.

나는 최대공약수를 다음과 같이 구해봤다.

1. A와 B의 값을 비교해 값이 큰 수를 최대값으로 지정한다.

int maxNum = (lcdNum0 > lcdNum1) ? lcdNum0 : lcdNum1;

2. 최대값까지 루프하면서 A와 B의 값 둘 다 나머지 값이 0으로 나눠지는 값을 구한다.

   한 가지 예를 들어보겠다.
   A = 4, B = 10 이면 B가 최대값이다.

   A(=4) 가 나머지 값이 0인 수 : 1 , 2 << , 4
   B(=10) 가 나머지 값이 0인 수 : 1 , 2 << , 5 , 10

   4와 10의 약수는 1,2 이다. 이 중 제일 큰 값인 2가 최대공약수이다. 이것을 코드로 옮겨 작성해보면 다음과 같이 작성 가능하다.

   int lcm = 0;
        for(int i = 1; i <= maxNum; i++) {
                if(lcdNum0 % i == 0 && lcdNum1 % i == 0) {
                        int gcd = i; // 두 수의 최대공배수
                    }
                }

3. 최대공약수를 구했으니 최소공배수를 구하면 된다.

lcm = lcdNum0 * lcdNum1 / gcd; /* A * B / 최대공약수 */

느낀 점 🤔

내가 푼 방법 외에도 유클리드 호제법이라는 알고리즘이 존재한 걸 알았다.

int gcd(int a, int b)
{
    while (b > 0)
    {
        int tmp = a;
        a = b;
        b = tmp%b;
    }
    return a;
}

220과 286의 최대공약수를 유클리드 호제법으로 구해본다면!

• 220은 286로 나누어 떨어지지 않는다. -> 286 / 220 의 나머지 값 : 66
• 286은 66으로 나누어 떨어지지 않는다. -> 286 / 66 의 나머지 값 : 22
• 66과 22는 나누어 떨어진다.
• 최대 공약수 : 22

이번 문제를 풀며 느낀 점은, 최대공약수를 구하는 것이 큰 관건이라는 것이였다.
다음에 이런 문제가 나오면 참고해보자.

• 참고 사이트
  • 백준 공식 사이트
  • Lonpeach Tech