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

🔗 문제 링크

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

---

📌 문제 개요

두 자연수 A와 B가 주어졌을 때, 두 수의 최소공배수(LCM) 를 구하는 문제
최소공배수란 두 수의 공통 배수 중 가장 작은 값을 의미

예시

입력  
6 8  

출력  
24

---

📌 접근 방법

최소공배수는 다음 공식을 이용하면 쉽게 구할 수 있다.

LCM(A,B) = (A × B) / GCD(A,B)

1. 두 수 입력
2. 유클리드 호제법을 이용해 최대공약수(GCD) 계산
3. 공식 (A / GCD) * B 로 최소공배수 계산

---

📌 핵심 아이디어

유클리드 호제법 : 두 수 a, b가 있을 때

gcd(a, b) = gcd(b, a % b)

이 과정을 b == 0이 될 때까지 반복하면, 최종적으로 a가 최대공약수가 된다.

gcd(6, 8)  

8 % 6 = 2  
6 % 2 = 0  

GCD = 2

---

📌 전체 코드

package no_13241;

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

public class No13241 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());

        System.out.println(a / gcd(a, b) * b);
    }

    static long gcd(long a, long b) {

        while (b != 0) {
            long temp = a % b;
            a = b;
            b = temp;
        }

        return a;
    }
}

---

📌 정리

• 최소공배수는 최대공약수(GCD) 를 이용해 쉽게 계산할 수 있다.
• 유클리드 호제법을 사용하면 O(logN) 시간으로 GCD를 구할 수 있다.
• (a * b) / gcd 대신 (a / gcd) * b 형태로 계산하면 오버플로우를 방지할 수 있다.