[백준] 1934 : 최소공배수 (JAVA)

문제

BOJ 1934 : 최소공배수 - https://www.acmicpc.net/problem/1934

풀이

유클리드 호제법을 사용하여 두 자연수 a, b의 최대공약수(GCD)를 구한 뒤, 두 수의 곱을 최대공약수(GCD)로 나누면 최소공배수(LCM)가 된다.

[유클리드 호제법(Euclidean algorithm)]
"2개의 자연수의 최대공약수(GCD)를 구하는 알고리즘"

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

즉, GCD(a, b) = GCD(b, a%b)이다. 재귀적으로 b가 0이 될때까지 반복하면 a와 b의 최대공약수를 구할 수 있다.

최소공배수 식 : a * b / GCD(a,b)

수학과가 아니기 때문에 증명은 패스한다.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            bw.write(LCM(a,b)+"\n");
        }
        bw.flush();
    }

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

    public static int LCM(int a, int b) {
        return a * b / GCD(a, b);
    }
}

정리

✔ 알고리즘 분류 - 수학, 정수론, 유클리드 호제법
✔ 난이도 - ⚪ Silver 5

🤦‍♀️ 오늘의 삽질리스트

• 사실 최소공배수, 최대공약수 나오는 문제들은 유클리드 호제법 사용하는 식을 알아두고 있으면 어렵지 않게 금방 풀 수 있다. 그런데 풀 때마다 애매하게 기억하고 계속 찾아본다. GCD(a, b) = GCD(b, a%b) 알아둘 것!

참고 사이트

[유클리드 호제법]
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95