[백준][Java] 1934번 최소공배수

안녕하세요 :)

적어도 하루 1개 이상 알고리즘 문제를 해결하려 노력하고 있습니다.

혼자 해결 가능한 문제도 있고, 어려웠던 문제도 있던 차라 복습하고자  글을 써 내려갑니다.

 

---

 

백준 1934 최소공배수

오늘 문제는 두 자연수 A와 B의 최소공배수(LCM : Least Common Multiple)를 구하는 문제이다.

입력으로 테스트 케이스 개수 T가 주어지고, 그 다음 줄주터 A, B 값이 T쌍 주어진다.

 

📘 문제

 

💡 해결 방법

최소공배수를 구하는 공식은 다음과 같다

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

따라서 두 수의 최대공약수(GCD)를 먼저 구해야 한다.

GCD는 유클리드 호제법을 사용하여 GCD를 빠르게 계산 가능하다.

 

* 유클리드 호제법 *
- 무조건 GCD(큰 수, 작은 수)로 시작해서 GCD(작은 수, 큰 수 % 작은 수)를 반복

- 두 수 a, b에 대해 GCD(a, b)는 GCD(b, a % b) 와 같다.

- 이 과정을 b가 0이 될 때까지 반복하면 a가 최대공약수가 된다.

예: GCD(24, 18)
→ GCD(18, 6)
→ GCD(6, 0)
→ 6

 

✅ 풀이 및 설명 (설명은 더보기 클릭)

풀이

• 최소공배수(LCM)를 구하기 위해 최대공약수(GCD)를 먼저 구해야 한다.
  
  • getGCD : 유클리드 호제법 사용하여 GCD를 구하는 함수를 만든다.
  • getLCM : 풀이의 정답인 최소공배수(LCM)을 구하는 함수를 만든다.
• getLCM 출력

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());  // 테스트 케이스 수

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

            // 최소공배수 출력
            System.out.println(getLCM(a, b));
        }

        br.close();
    }

    // 최대공약수(GCD)를 구하는 함수 - 유클리드 호제법 사용
    private static int getGCD(int a, int b) {
        if (b == 0) return a;
        return getGCD(b, a % b);
    }

    // 최소공배수(LCM)를 구하는 함수
    private static int getLCM(int a, int b) {
        return (a * b) / getGCD(a, b);
    }
}

 

이 문제는 최대공약수와 최소 공배수의 관계를 알고 있다면 아주 쉽게 풀 수 있다.

유클리드 호제법은 효율적이고 자주 쓰이므로 반드시 숙지해두자.

문제에서 주어지는 수의 법위가 크지 않기 때문에 int 타입으로도 충분이 계산이 가능하다.

 

---

공부하면서 유용했던 부분 메모 겸 공유하고자 끄적입니다.

고쳐야 하는 부분 있다면 댓글 남겨주시면 수정하겠습니다.

행복한 하루 보내세요 (❁´◡`❁)