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

코드 힌트

1. 최소 공배수 계산:
   • 두 숫자의 최소 공배수(LCM)를 구하기 위해 먼저 최대 공약수(GCD)를 계산합니다.
   • GCD를 이용하여 두 숫자의 LCM을 간단히 구할 수 있습니다.
2. 반복 처리:
   • 여러 쌍의 숫자에 대해 LCM을 계산해야 하므로, 입력된 쌍의 숫자에 대해 반복적으로 LCM을 계산하고 출력합니다.
3. 재귀를 이용한 GCD 계산:
   • 유클리드 알고리즘을 사용하여 GCD를 재귀적으로 계산합니다.
   • 이 방법은 두 숫자 중 하나가 0이 될 때까지 계속 나머지를 구하는 방식입니다.

 

---

정답은 더보기 클릭

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        // BufferedReader와 BufferedWriter를 사용해 입출력 처리
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입력된 숫자 쌍의 개수 n을 입력받음
        int n = Integer.parseInt(br.readLine());
        
        // n번 반복하여 각 숫자 쌍에 대해 LCM을 계산하고 출력
        for (int i = 0; i < n; i++) {
            // 한 줄에 입력된 두 수를 공백으로 분리하여 배열에 저장
            String[] arr = br.readLine().split(" ");
            
            // 첫 번째 숫자와 두 번째 숫자를 각각 a, b로 파싱
            int a = Integer.parseInt(arr[0]);
            int b = Integer.parseInt(arr[1]);
            
            // 두 수의 LCM을 계산하여 출력
            bw.write(lcm(a,b) + "\n");
        }
        
        // BufferedWriter의 남은 데이터를 출력
        bw.flush();
        bw.close();
    }
    
    // 최대 공약수를 계산하는 재귀 함수
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);  // 유클리드 알고리즘
    }
    
    // 최소 공배수를 계산하는 함수
    public static int lcm(int a, int b) {
        return a * b / gcd(a,b);  // a * b를 GCD로 나누어 LCM 계산
    }
}