[백준] - 최대공약수와 최소공배수 (2609) (자바/Java)

 

 

 

 

 

 

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

2609번: 최대공약수와 최소공배수

 

 

 

 

문제.

---

 

 

 

 

 

 

 

 

풀이.

---

 

 

이번 문제는 처음에 제출했는데 틀렸던 코드를 보여주겠다...(너무 단순 + 멍충,,,)

<오답>

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();

        int rs = num1 % num2;
        int rs2 = (num1 * num2) / rs;

        System.out.println(rs);
        System.out.println(rs2);

    }

}

조금 창피하지만 이렇게라도 공개처형 당해야 더 생각하고 더 열심히 할 것이다...😭

 

<정답>

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();

        int gcd = getGCD(num1, num2);

        System.out.println(gcd);
        System.out.println((num1 * num2) /gcd);

    }

    public static int getGCD(int num1, int num2) {
        if (num1 % num2 == 0) {
            return num2;
        }
        return getGCD(num2, num1 % num2);
    }

}

찾아보면서 문제를 풀다 이번에 접하게된 것은 ' 최대공약수 GCD ' 이다.

 

 

최대공약수 GCD

 

GCD는 가장 큰 공통된 약수라는 뜻이다.

 

" a와 b 두 수가 주어지면 a의 약수들을 모두 구하고, b의 약수들을 모두 구한 뒤 공통 된 약수들만 찾아내어 약수들의 곱으로 다시 나타내준다. "

 

하지만 단점이 있다. 약수가 많을 경우 그것을 인수분해 하는데 시간을 많이 필요로 하게 되며 또한 두 수를 비교한 뒤 다시 곱해주는 것도 너무 많은 시간을 소비하게 된다. 그래서 최대공약수 또는 최소공배수를 사용하기 위해 보통은 앞서 보여준 알고리즘 방식을 사용하게 된다.  그게 바로 '유클리드 호제법'이다.

 

 

유클리드 호제법

 

2개 수의 최대공약수를 구하는 알고리즘이다.

자연수 a, b에 대해서 a를 b로 나눈 나머지를 c라 한다면 a,b의 최대공약수와 b,c의 최대공약수는 같다.

이 성질에 따라 a를b로 나눈 나머지 c를 구하고, b를 c로 나눈 나머지 c를 구한다.

나머지가 0이 될 때 나눈 수가 a, b의 최대공약수가 된다.

 

최소 공배수 : (a X b) / (최대공약수)

 

ex) 24, 18의 최대공약수 :      24 % 18 = 6      18 % 6 = 0 //최대 공약수 = 6

 

//최소 공배수 : (24 X 18) / 6 = 72

 

이런 식으로 풀게 되면 위 코드로 정답이다!!!