[백준 문제 풀이] 1934번 최소공배수

Junu Kim·2026년 1월 2일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

80/89

[1934] 최소공배수

난이도: ★★☆☆☆ • solved on: 2026-01-02

문제 요약

문제 유형: 유클리드 호제법, 수학
요구사항: 테스트 케이스마다 두 자연수의 최소공배수(LCM) 를 출력해야 한다.

사용 개념

자료구조
- StringTokenizer, StringBuilder
알고리즘/기법
- 최대공약수 (GCD)
- 최소공배수 (LCM) 관계식: $LCM(a,b) = (a / GCD(a,b)) * b$
핵심 키워드
- 유클리드 호제법 (Euclidean Algorithm)
- 공약수/공배수

풀이 아이디어 및 코드

방법 1 : 공통 인수 탐색

문제 분해

두 수의 공약수를 작은 값부터 나눠가며 공통 인수를 result에 누적한다.

나눠 떨어지면 a, b를 그 인수로 나누고, 나눠 떨어지지 않을 때만 divisor++ 한다.
핵심 로직 흐름
result = 1
divisor = 2
while divisor < a or divisor < b:
    if a%divisor==0 and b%divisor==0:
        result *= divisor
        a /= divisor
        b /= divisor
    else:
        divisor++
result *= a*b
예외 처리

한 수가 다른 수의 배수인 경우, 더 큰 수가 LCM이므로 바로 출력한다.

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

class Main {
    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();
        int a = 0;
        int b = 0;
        int result = 1;

        for(int i = 0; i < n; i++){
            String[] lines = br.readLine().split(" ");

            a = Integer.parseInt(lines[0]);
            b = Integer.parseInt(lines[1]);
            result = 1;

            if(a%b == 0 || b%a == 0){
                sb.append(Math.max(a,b)).append("\n");
                continue;
            }
            int min = Math.min(a, b);
            int divisor = 2;
            while(divisor < a || divisor < b){
                if(a%divisor==0 && b%divisor==0){
                    result *= divisor;
                    a /= divisor;
                    b /= divisor;
                } else {
                    divisor++;
                }
            }

            result *= a * b;
            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }
}

방법 2 : 유클리드 호제법으로 GCD → LCM

문제 분해

최소공배수는 공약수를 “직접” 모두 찾기보다, 최대공약수(GCD) 만 구하면 바로 계산할 수 있다.
핵심 로직 흐름
gcd(a,b):
    while b != 0:
        t = a % b
        a = b
        b = t
    return a

lcm = a / gcd(a,b) * b
예외 처리

곱이 커질 수 있으므로 long을 사용한다.

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

class Main {
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());

            long g = gcd(a, b);
            long l = (a / g) * b;   // overflow 방지를 위해 a/g 먼저 수행
            sb.append(l).append('\n');
        }
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1 :

시간 복잡도: 최악 O(max(a,b))에 가깝게 커질 수 있다. (작은 약수부터 전부 시도하는 구조)
공간 복잡도: O(1)

방법 2 :

시간 복잡도: O(log(min(a,b))) (유클리드 호제법)
공간 복잡도: O(1)

어려웠던 점

처음에는 for (divisor++)로 약수를 검사했는데, 이 방식은 같은 소수가 여러 번(예: p²) 나눠지는 경우를 연속으로 반영하기 어렵다는 문제가 있었다.
그래서 “약수를 찾지 못할 때만 ++ 한다”는 방식으로 while로 바꿔 중복 약수를 처리하도록 수정했다.