[백준] 1934 자바 : 최소공배수

[백준] 1934 자바 : 최소공배수

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

---

문제.

 

테스트 케이스 갯수를 입력받아 각각의 값에 따른 최소공배수를 출력하면 되는 문제다.

---

풀이.

유클리드 호제법을 사용해 최대공약수를 구하고, 이를 활용해 최소공배수를 구할 수 있도록 하자.

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 《원론》 제7권, 명제 1부터 3까지에 해당한다.
출처 : 위키백과

역시나 개념은 어렵다...

쉽게 설명하면 두 정수 N, M 이 주어졌을 때 나머지가 0이 될 때 까지 N을 M으로 나눠서 나머지를 구하고 N과 M값을 각각 M, N%M 으로 바꿔주면 된다. 이 때 N값이 최대공약수가 된다. 

이를 간단히 코드로 짜보면 아래와 같다.

    public int gcd(int n, int m) {
        int temp;
        do {
            temp = n % m;
            n = m;
            m = temp;
        } while(temp != 0);
        return n;
    }

이렇게 최대공약수(GCD)를 구했다면 최소공배수(LCM)을 구하는건 어렵지 않다. 

두 수 M, N을 곱하고 이를 최대공약수(GCD)로 나누어 주면 끝이다. 

소인수분해보다 속도가 더 빠르다고 하니 가급적 유클리드 호제법을 사용하도록 하자!

---

코드.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, m, T;
        T = sc.nextInt();
        for(int i = 0; i < T; i++) {
            n = sc.nextInt();
            m = sc.nextInt();
            int gcd = gcd(n, m);
            int lcm = n * m / gcd;
            System.out.println(lcm);
        }
    }
    // 최대 공약수 (유클리드 호제법)
    public static int gcd(int n, int m) {
        int temp;
        do {
            temp = n % m;
            n = m;
            m = temp;
        } while(temp != 0);
        return n;
    }
}

 

---

난이도 : ◐○○○○○○○○○

지극히 주관적인 생각