[백준 2024/01/20] 1934번 최소공배수 + 유클리드 호제법

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

1934번: 최소공배수

 

1. 접근 방법

쉽게 드는 생각으로는,

for(int i = a*b; i>=Math.max(a,b);i-=Math.max(a,b))

a*b에서부터 a와 b 중의 최대값에 도달할 때까지 둘 중의 더 큰 값으로 빼주는 방법이었다.

 i%a==0이고 i%b==0 일 때, list에 넣어두고,

list에서 최소값을 찾아 출력하는 방법이었다.

rough draft

 

해당 방법으로 구현 했을 때, 문제를 맞히긴 했지만, 

알고리즘 분류에 "유클리드 호제법" 이라는 것이 있어서 이에 대해서도 언급하여 보도록 할 것이다.

 

1) 유클리드 호제법 - 최대공약수

두 정수의 최대공약수를 쉽게 알아내는 방법이다.

2개의 자연수 a, b (a>b)에 대해서,

a%b = r 일 때,

b와 r의 최대공약수 = a와 b의 최대 공약수 인 것이다.

따라서 위 과정을 반복하다가 나머지가 0이 되었을 때, 나누는 수가 a와 b의 최대공약수 인 것이다.

 

이를 10과 6의 최대공약수를 구하는 과정을 통해 이해해 보도록 할 것이다.

10%6 = 4

6%4 = 2

4%2 = 0

이 때, 2가 최대공약수가 된다.

 

2) 유클리드 호제법 - 최소공배수

G를 최대공약수라고 해보자,

a = Gx, b= Gy 이다.

a*b = GGxy 가 된다.

ab/G = Gxy = 최소공배수

즉, a와 b로 곱한 값을 최대공약수로 나눈 값이 최대 공약수가 되는 것이다.

 

따라서 lcm(a,b) = a*b/gcd(a,b) 이다.

 

chatGPT에게 Java의 lcm, gcd 구현 여부를 알아보았다.

 

최대공약수의 경우, BigInteger클래스의 gcd메서드를 사용하면 되었다.

하지만 lcm의 경우 gcd를 이용하여 구해야 했다. lcm(a,b) = a*b/gcd(a,b)

 

public class Main {
    public static void main(String[] args) {
        int num1 = 60;
        int num2 = 48;

        int lcm = lcm(num1, num2);

        System.out.println("최소공배수: " + lcm); // 출력: 최소공배수: 240
    }

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

    public static int lcm(int a, int b) {
        return a * (b / gcd(a, b));
    }
}

 

다시 원래 문제로 돌아와서, 다음은 1934번 코드이다.

만약 유클리드 호제법을 적용한다면 코드가 더 간단해지지 않을까 싶다. -> 메모리, 시간 측면에서 나은 결과를 보여주었다.

2. 코드 -1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Collections;



public class b1934 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(reader.readLine());


        for(int i =0; i<num;i++){
            String line = reader.readLine();
            String[] line_s = line.split("\\s+");
            System.out.println(min_mul(Integer.parseInt(line_s[0]),Integer.parseInt(line_s[1])));

        }
    }

    public static int min_mul(int a, int b){
        List<Integer> list = new ArrayList<>();
        for(int i = a*b; i>=Math.max(a,b);i-=Math.max(a,b)){
            if((i%a==0)&&(i%b)==0){
                list.add(i);
            }
        }
        return Collections.min(list);
    }

}

 

유클리드 호제법 적용 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Collections;



public class b1934 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(reader.readLine());


        for(int i =0; i<num;i++){
            String line = reader.readLine();
            String[] line_s = line.split("\\s+");
            System.out.println(lcm(Integer.parseInt(line_s[0]),Integer.parseInt(line_s[1])));

        }
    }

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


    public static int lcm(int a, int b){
        return a*b/gcd(a,b);
    }

}