[백준] - 최소공배수 (1934) (자바/Java)

 

 

 

 

 

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

1934번: 최소공배수

 

 

 

 

문제.

---

 

 

 

풀이.

---

 

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        
        for (int i = 0; i < num; i++) { //3개의 최소공배수 구하기 위한 반복
            int a = sc.nextInt();
            int b = sc.nextInt();
            int gcd = gcdGet(a,b); //최대공약수

            System.out.println((a*b) / gcd); //최소공배수
        }

    }

    static int gcdGet(int a, int b) { // 최대공약수
        if (a % b == 0) {
            return b;
        }
        return gcdGet(b, a % b);
    }
}

 

최소공배수 구하기 문제.

 

이번 문제에서도 전에 풀었던 문제 중 최소공배수와 최대공약수 문제가 있다. 그 문제처럼 "유클리드 호제법"을 사용해 풀 것이다.

 

<A, B의 최대공약수>

A % B = C

B % C = 0 //최대공약수 = C 

 

<최소공배수>

(A * B) / C(최대공약수)

 

https://luke-king.tistory.com/42 

[백준] - 최대공약수와 최소공배수 (2609) (자바/Java)

유클리드 호제법 설명글은 위 글에 작성해 뒀다.

 

풀이를 말하자면

 

최대공약수 : 24 % 18 = 6      18  % 6 = 0    최대공약수 = 6

최소공배수 : (24 * 18) / 최대공약수(6)        최소공배수 = 72이다.

 

이런 식으로 풀면 쉽게 풀 수 있다.