[Java] 백준 2609번: 유클리드 호제법

브루트 포스

import java.io.*;
import java.util.StringTokenizer;

public class Problem2609 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int num1 = Integer.parseInt(st.nextToken());
        int num2 = Integer.parseInt(st.nextToken());
        int min = Math.min(num1, num2); // 더 작은 정수

        for (int i = min; i > 0; i--) {
            if (num1 % i == 0 && num2 % i == 0) {
                int GCD = i; // 최대 공약수
                int LCM = Math.abs(num1 * num2) / GCD; // 최소 공배수
                System.out.println(GCD);
                System.out.println(LCM);
                break;
            }
        }
    }
}

---

최소 공배수 공식

---

유클리드 호제법

 

▶ 두 수의 최대 공약수를 구하는 알고리즘이다. 두 수를 나누어 나머지를 반복적으로 구하는 방식을 따른다.

 

 두 수 a와 b가 있을 때, a를 b로 나눈 나머지를 r이라고 할 때, a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다. 이 과정을 반복해 나머지가 0이 될 때, 나누는 수 b는 최대 공약수가 된다.

// 유클리드 호제법
static int calculateGCD(int a, int b) {
    while (b != 0) {
        int r = a % b; // 나머지

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

---

유클리드 호제법 응용

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

import java.util.Scanner;

public class Problem1735 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n1 = sc.nextInt();
        int d1 = sc.nextInt();
        int n2 = sc.nextInt();
        int d2 = sc.nextInt();

        int newN = (n1 * d2) + (n2 * d1);
        int newD = d1 * d2;

        int GCD = calGCD(newN, newD);
        System.out.println(newN / GCD + " " + newD / GCD);
    }

    static int calGCD(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

▶ 이런 식으로 기약분수 만들 때 사용해도 유용하다.