[백준: 알고리즘_Java] 2609번_최대공약수와 최소공배수

 

<문제>

 

---

<풀이>

 

처음에 문제를 딱 봤을땐 아 개쉽네~~ㅋㅋ 이었지만

살짝 더 생각해보니....어라라? 어떻게 구하드라...? 가 되어버렸다.

그래서 급하게 한 구글링..

 

어떻게 최소 공배수를 구할 수 있을깡??

 

※ 방법은 바로 유클리드 호제법!! 이다,,

(이름은 초면이지만.. 사실 1학기 이산수학때 살짝 배웠었네..엽!)

 

♠ 호제법인 이유~~식이?

서로 호, 나눌 제 -> 서로 나눈다앙~

 

1. r = A % B (%: 나눈 나머지)
2. GCD(A, B) = GCD(B, r)

~를 이용하면 되미당!!

 

 

예시 
GCD(581, 322) = GCD(322, 259) = GCD(259, 63) =  GCD(63, 7) = GCD(7, 0) = 7 (-> 최대공약수)

 

원리를 설명해 보자미언.. 살짝 복잡식이 그시기하긴 한데..

큼큼.

 

GCD(A, B) = d라 가정.
A = ad, B = bd 라 할 수 있다.
-> a, b는 서로소. (d가 최대공약수니깐)

A = Bq+r 이라 할 수 있고, 이걸 이항하면
r = A-Bq = (a-bq)d .
그렇다면??? B와 r은 d를 공통된 약수로 같는드앙!!
(최대인지는 b와 a-bq가 서로소인지 귀류법으로 증명하면 됨. 생략하겠음)

짜잔~~ 끝났식이.

 

근데 코드로 짜는 법은 반복문을 이용하는 방법과 재귀를 이용하는 방법이 있는데,

반복문이 더 빨라서 그걸 이용했다.

 

그다음...!

최소공배수는?!

 

쉬워용~

 A = ad, B = bd 라 했으니
 a * b * d 가 최소 공배수임
 그런데 a, b는 따로 안 구했으니깡
 A * B /GCD(A, B) (= ad * bd / d)

 

 

import java.util.*;
public class GCD_LCM {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        System.out.println(GCD(a, b));
        System.out.println(LCM(a, b));



    }
    //최대공약수
    public static int GCD(int a, int b) {
        while(b != 0) {
            int r = a%b;

            //GCD(a, b) = GCD(b, r)
            a = b;
            b = r;
        }
        return a;
    }

    //최소공배수
    public static int LCM(int a, int b) {

        return a*b/GCD(a, b);
    }
}

 

 

---

<결과>

 

음하하하하