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

안녕하세요 :)

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

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

 

---

 

백준 13241 최소공배수

오늘 문제는 두 정수 A와 B가 주어졌을 때, 최소공배수(LCM)를 구하는 문제입니다.

대신, A와 B의 범위가 굉장히 크기 때문에 일반적인 int 타입을 사용하면 오버플로우가 발생할 수 있습니다.

 

📘 문제

 

💡 해결 방법

최소공배수 구하는 공식은 이전 문제인 1934번 최소공배수(아래 링크) 문제와 동일합니다.

단, 곱셈 연산에서 오버플로우를 방지하기 위해 long 타입을 사용해야합니다.

 

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

• 최소공배수(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));
        
        // 두 수 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());

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

        br.close();
    }

    // 유클리드 호제법으로 최대공약수(GCD) 계산
    private static long getGCD(long a, long b) {
        if (b == 0) return a;
        return getGCD(b, a % b);
    }

    // 최소공배수(LCM) 계산
    private static long getLCM(long a, long b) {
        return (a * b) / getGCD(a, b);
    }
}

 

이전에 풀었던 1934번 문제(최소공배수)와 거의 같은 로직이지만,

입력 범위가 커졌기 때문에 자료형 선택이 중요한 문제입니다.

실수로 int를 썼다면 틀릴 수 있으니 항상 문제의 입력 조건을 확인해야합니다.

 

---

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

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

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