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

문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

---

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

---

예제 입력 1 

3
1 45000
6 10
13 17

예제 출력 1

45000
30
221

 

 

 

내가 푼 코드

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

public class Main {
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(br.readLine());
      
      for (int i=0; i<N; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int A = Integer.parseInt(st.nextToken());
          int B = Integer.parseInt(st.nextToken());
          
          System.out.println(getCalculation(A, B));
      }
    }
    
    // 최소공배수 = (A * B) / A와B의 최대공약수
    public static int getCalculation(int A, int B) {
        int max = A > B ? A : B;
        int min = A < B ? A : B;
        int r = -1;
        // 최대공약수 구하기 (max)
        while (true) {
            // 나머지가 0이면 반복문 종료료
            if (r == 0) 
                break;
            
            r = max % min;
            max = min;
            min = r;
        }
        return (A * B) / max;
    }
}

 

 

풀이방법

 

최소공배수 구하는 공식 =  (A x B) / A와 B의 최대공약수

 

최대공약수를 구하는 방법은 유클리드 호제법이라고 유명한 알고리즘이 있다.

 

예를 들어 A = 90, B = 24라면 아래와 같이 나머지가 0이 될때 B의 값인 6이 최대공약수가 된다. ( A  > B 인 경우)

A	%	B	=	나머지
90		24		18
24		18		6
18		6		0

 

 

위의 코드에서 getCalculation(A, B) 중 큰값을 max, 작은값을 min에 주고 while문을 이용하여 r(나머지)이 0일때까지 반복문을 돌린다.

 

max의 값은 min의 값이 되게 되고 min은 다음 계산을 위하여 r이 되게 되는데 r == 0인 경우 max = 6, r과 min = 0이 되므로

이때 max가 최대공약수가 되게된다.

 

최대공약수를 구한 다음 최소공배수 공식에 넣어서 출력하면 끝