[백준(Java)] 13241. 최소공배수 (유클리드 호제법)

문제

정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다.

예:

• 10은 5의 배수이다 (5*2 = 10)
• 10은 10의 배수이다(10*1 = 10)
• 6은 1의 배수이다(1*6 = 6)
• 20은 1, 2, 4,5,10,20의 배수이다.

다른 예:

• 2와 5의 최소공배수는 10이고, 그 이유는 2와 5보다 작은 공배수가 없기 때문이다.
• 10과 20의 최소공배수는 20이다.
• 5와 3의 최소공배수는 15이다.

당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다.

입력

한 줄에 두 정수 A와 B가 공백으로 분리되어 주어진다.

50%의 입력 중 A와 B는 1000(103)보다 작다. 다른 50%의 입력은 1000보다 크고 100000000(108)보다 작다.

추가: 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오. C/C++에서는 long long int를 사용하고, Java에서는 long을 사용하시오.

출력

A와 B의 최소공배수를 한 줄에 출력한다.

 

예제 입력

3 5

 

예제 출력

15

 

내 풀이

 

import java.util.Scanner;

class Main {

    // 최대 공약수
    public static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    // 최소 공배수
    public static long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Long a = sc.nextLong();
        Long b = sc.nextLong();

        System.out.println(lcm(a, b));

        sc.close();
    }
}

 

입력으로 주어진 두 수의 최소공배수를 출력하는 간단한 프로그램이다. 두 수의 최소공배수는 (두 수의 곱) / (두 수의 최대공약수) 로 계산할 수 있다. 위의 코드에선 최대공약수를 gcd, 최소공배수를 lcm으로 선언하였다.

두 수의 최대공약수를 계산하기 위해서는 유클리드 호제법을 사용하는 것이 가장 잘 알려진 방법이다.

결론 및 정리

1) 유클리드 호제법이란?

 

두 정수 a, b (a ≥ b)의 최대공약수 GCD(a, b)는 GCD(b, a % b) 와 같다는 성질을 반복해서 b가 0이 될 때까지 계산하는 알고리즘.

 

2) 예시 

1. gcd(48, 18)
2. → gcd(18, 48 % 18) → gcd(18, 12)
3. → gcd(12, 18 % 12) → gcd(12, 6)
4. → gcd(6, 12 % 6) → gcd(6, 0)
5. → b == 0 이므로, 결과는 6

 

3) 코드 분석

public static long gcd(long a, long b) {
    while (b != 0) {
        long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

 

• a % b 를 계속해서 a와 b에 대입하면서
• b == 0이 될 때까지 반복
• 마지막에 남은 a가 바로 최대공약수

깃허브 주소

https://github.com/Chaehyunli/BaekJoon/tree/main/%EB%B0%B1%EC%A4%80/Silver/13241.%E2%80%85%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98