[코딩테스트] 백준 1934 자바

백준 1934

백준 1934 문제

최소 공배수는 A와 B가 주어졌을 때 A * B / 최대 공약수를 계산하여 구할 수 있다. 결국 이 문제는 유클리드 호제법을 이용해 최대 공약수를 구한 후 두 수의 곱에서 최대 공약수를 나눠 주는 것으로 해결할 수 있다.

import java.util.*;

public class Boj1934 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt(); // 테스트 케이스

        for (int i = 0; i < t; i++) { // t만큼 반복
            int a = sc.nextInt(); // 1번째 수
            int b = sc.nextInt(); // 2번째 수
            int result = a * b / gcd(a, b); // 결괏값

            System.out.println(result); // 결괏값 출력
        }
    }

    // 최대공약수를 구하는 메서드
    private static int gcd(int a, int b) {
        if (b == 0) { // b가 0이면
            return a; // a가 최대 공약수
        } else {
            return gcd(b, a % b); // 재귀 함수 형태로 구현
        }
    }
}

풀이

1. 테스트 케이스의 수를 입력 받아 t에 저장한다.
2. t만큼 반복하며 1번째 수를 a에 2번째 수를 b에 저장한다.
3. 최대 공약수를 구하는 메서드인 gcd() 메서드에 a와 b를 인자로 넘겨주어 결괏값을 result에 저장한다.
   3-1. gcd() 메서드는 매개변수 a와 b로 인자를 받고 b가 0이라면 a가 최대 공약수이기 때문에 a를 반환한다.
   3-2. b가 0이 아니라면 최대 공약수가 아직 나오지 않았기 때문에 작은 수 b와 큰 수 a에서 b로 나눈 나머지(a % b)를 두 번째 인자로 넘겨주어 재귀 함수 형태로 최대 공약수를 구한다.
4. 결괏값을 출력한다.