[백준][Java] 2609 - 최대공약수와 최소공배수

문제 링크

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

---

문제 풀이 과정

최대공약수와 최소공배수 문제에 대해 효율적으로 풀기 위해서는 유클리드 호제법에 따라 최대공약수를 푸는 방법에 대해 알아야 손쉽게 풀 수 있다.

유클리드 호제법이란 2개의 자연수에 대한 최대공약수를 구하는 방식이다. 쉽게 설명하면 두 수 a,b에 대해서 더 작은 수로 나눈 나머지로 끊임없이 0이 될때까지 나누는걸 의미한다. 이걸 쉽게 설명하려면 아래 예시가 가장 쉽게 이해가 된다.

1. 1500 ÷ 326

• 1500을 326으로 나눈 몫은 4이고, 나머지는 196이야.
• 즉, 1500 ÷ 326 = 4 (몫), 나머지 196

2. 326 ÷ 196

• 이제 326을 196으로 나눠. 몫은 1이고, 나머지는 130이야.
• 즉, 326 ÷ 196 = 1 (몫), 나머지 130

3. 196 ÷ 130

• 196을 130으로 나누면, 몫은 1이고, 나머지는 66이야.
• 즉, 196 ÷ 130 = 1 (몫), 나머지 66

4. 130 ÷ 66

• 130을 66으로 나누면, 몫은 1이고, 나머지는 64야.
• 즉, 130 ÷ 66 = 1 (몫), 나머지 64

5. 66 ÷ 64

• 66을 64로 나누면, 몫은 1이고, 나머지는 2야.
• 즉, 66 ÷ 64 = 1 (몫), 나머지 2

6. 64 ÷ 2

• 마지막으로 64를 2로 나누면, 몫은 32이고 나머지는 0이 돼.
• 즉, 64 ÷ 2 = 32 (몫), 나머지 0

결과:

나머지가 0이 되었으므로, 이때 나누는 수인 2가 1500과 326의 **최대공약수(GCD)**야.

정리:

• **1500과 326의 최대공약수(GCD)**는 2!

예시처럼 끊임없이 나누다보면 나머지가 0이 되는 순간이 곧 최대공약수인 지점이다. 최대공약수를 구했다면 최소공배수는 구하기 쉽다. 정리하면 다음과 같다.

• 최소공배수 : 두 수 a * b / GCD(a,b)
• 최대공약수 : 유클리드 호제법에 따라 나머지가 0인 지점의 나누는 수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class solution2609 {

    // 최소공배수와 최대공약수
    // 최대공약수는 유클리드 호제법에 따라
    // GCD(a,b) = GCD(b,a, mod b)
    // lcm(a,b) = a * b / GCD(a,b)
    public static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] targetArray = new int[2];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        targetArray[0] = Integer.parseInt(st.nextToken());
        targetArray[1] = Integer.parseInt(st.nextToken());

        System.out.println(gcd(targetArray[0], targetArray[1]));
        System.out.println(lcm(targetArray[0], targetArray[1]));
    }
}

---

참고

05. 유클리드 호제법