[Java] 백준알고리즘 #13241 최소공배수

백준알고리즘 #13241 최소공배수

백준알고리즘 #13241 최소공배수

백준알고리즘 #13241 최소공배수

 

문제 설명에서 알 수 있듯이, 유클리드 호제법을 이용해 최소공배수를 구하는 문제이다.

 

먼저 유클리드 호제법에 대해 알아보자.

출처 : 위키백과 (https://ko.wikipedia.org)

유클리드 호제법을 이용해 최대공약수를 구할 수 있다.

최대공약수를 구하면 자연스럽게 최소공배수도 구할 수 있는데,

예를 들어 35와 100의 경우

100을 35로 나눈 나머지 -> 30

35를 30으로 나눈 나머지 -> 5

30을 5로 나눈 나머지 -> 0

따라서 최대공약수는 5가 되고, 이를 이용해 최소공배수를 구하면

35 x 100 / 5 = 700 이 된다.

 

먼저 유클리드 호제법을 이용해 최대공약수를 구하는 식은 다음과 같다.

long a = sc.nextInt();
long b = sc.nextInt();
long gcd = 0; // 최대공약수

if (a > b) {
    long tmp = a;
    a = b;
    b = tmp;
}
while (true) {
    long tmp = b % a;
    if (tmp == 0) {
        gcd = a; // 나머지가 0이면 최대공약수
        break;
    }
    b = a;
    a = tmp;
}

두 수 중 작은 수를 a, 큰 수를 b라고 하고, b에서 a를 나눈 나머지를 tmp에 저장한다.

이 tmp가 0이 아니라면, b에 a를 저장, a에 tmp를 저장하고 다시 b를 a로 나눈다. (0이 될때까지 반복)

 

이제 여기서 구한 최대공약수를 이용해 최소공배수를 구하면 된다.

 

long lcm = a * b; // 최소공배수
... // 중략
lcm = lcm / gcd;

 

전체 코드는 다음과 같다.

 

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextInt();
        long b = sc.nextInt();
        long gcd = 0; // 최대공약수
        long lcm = a * b; // 최소공배수

        if (a > b) {
            long tmp = a;
            a = b;
            b = tmp;
        }
        while (true) {
            long tmp = b % a;
            if (tmp == 0) {
                gcd = a; // 나머지가 0이면 최대공약수
                break;
            }
            b = a;
            a = tmp;
        }
        lcm = lcm / gcd;
        System.out.println(lcm);

        sc.close();
    }
}