문제 출처

단계별로 풀어보기 > 약수, 배수와 소수 2 > 최소공배수
https://www.acmicpc.net/problem/1934

문제 설명

두 자연수 A,B가 주어질 때, A,B의 최소공배수를 구하라.

접근 방법

최대공약수를 구하는 방법인 GCD(유클리드 호제법)을 이용하여
최소공배수를 구하는 방법 LCM을 구현한다.

GCD는 어떤 수의 공약수는 그 나머지의 공약수임을 이용하는 방법으로
a와 b가 있을 때, GCD(a, b) = GCD(b, a % b) 를 반복하여 b가 0이 되는 경우 a가 최대공약수가 됨을 이용한다.
a = 48, b = 18일 때,

48 = 18 × 2 + 12
18 = 12 × 1 + 6
12 = 6 × 2 + 0

을 통해 과정을 알 수 있다.

LCM은
두 수 a,b의 곱은

a * b = GCD(a, b) * LCM(a, b)

로 나타낼 수 있는데, 이를 변형하면

LCM(a, b) = (a * b) / GCD(a, b)

로 나타난다.

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

public class 최소공배수 {

    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));
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            sb.append(lcm(a,b)).append("\n");
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }
}

알게된 점

LCM과 GCD에 대해서 알게 되었고, 관계 또한 알게 되었다.
또한 GCD 와 LCM의 시간 복잡도는 각각 O(log min(a,b)) 이므로 반복횟수 N번와 같이 시간복잡도를 계산하면
O(NlogM) 이다.(min(a,b) -> M)

문제푼 흔적