[1934] 최소공배수

✔ 최소공배수

[백준 1934]

문제 분석하기

최소 공배수는 A와 B가 주어졌을 때 'A * B / 최대 공약수'를 계산해 구할 수 있으므로

유클리드 호제법을 이용해 최대 공약수를 구한 후 두 수의 곱에서 최대 공약수를 나눠 주어 최소 공배수를 구하도록 함

손으로 풀어보기

1. 유클리드 호제법을 이용해 A, B의 최대 공약수를 구함
2. 두 수의 곱을 최대 공약수로 나눈 값을 정답으로 출력

슈도코드 작성하기

t(테스트 케이스)
for(t만큼 반복하기) {
    a(1번째 수) b(2번째 수)
    결괏값 = a * b / gcd(a, b)
    결괏값 출력하기
}
gcd {
    if(b가 0이면) a가 최대 공약수
    else gcd(작은 수, 큰 수 % 작은 수)
}

코드 구현하기

/**
 * 1934) 최소공배수
 */
public class D042_1934 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // t(테스트 케이스)
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            // a(1번째 수)
            int a = sc.nextInt();
            // b(2번째 수)
            int b = sc.nextInt();
            // 결괏값 = a * b / gcd(a, b)
            int result = a * b / gcd(a, b);
            // 결괏값 출력하기
            System.out.println(result);
        }
    }

    // 최대 공약수 함수 구현하기
    public static int gcd(int a, int b) {
        // if(b가 0이면)
        if (b == 0)
            // a가 최대 공약수
            return a;
        else
            // gcd(작은 수, 큰 수 % 작은 수)
            return gcd(b, a % b);
    }
}