백준_1934 최소공배수 (유클리드 호제법)

 

gcd 메서드에서는 a>b 임을 가정하고 진행하지만,

슈도 코드를 보면 a와 b의 크기를 비교하여 gcd메서드에 넘기지 않음을 볼 수 있다.

 

이는 손으로 한번만 따라 풀면 단번에 이해할 수 있음.

gcd(6, 10) -> gcd(10, 6)

 

즉, a<b로 값이 들어가도 재귀호출을 통해 결국 a>b로 됨.

 

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

public class BJ_1934_최소공배수 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        int a, b;
        StringTokenizer st;
        for (int i=0; i<t; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            sb.append(a*b/gcd(a, b)).append('\n');
        }

        System.out.println(sb);
    }

    static int gcd(int a, int b) { // 유클리드 호제법
        if (b==0) {
            return a;
        }
        return gcd(b, a%b); // mod연산 결과가 0이면 더 작은 b를 반환하게 된다.
    }
}

1934번: 최소공배수