백준 1934 최소공배수

문제

풀이

public class Q1934_최소공배수 {

    static int tmp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());
        int result = 0;
        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            int min = Integer.parseInt(st.nextToken());
            int max = Integer.parseInt(st.nextToken());
            gcd(min, max);
            // 최소공배수를 구하는 수식
            result = max * min / tmp;
            System.out.println(result);
        }
    }
	
    // 최대공약수를 구하는 함수(유클리드 호제법)
    public static void gcd(int min, int max) {
        if (min == 0) {
            tmp = max;
            return;
        }
        int nam = max % min;
        gcd(nam, min);
    }
}

리뷰

유클리드 호제법을 사용하면 쉽게 풀 수 있는 문제였다.
유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘이다.

나머지 연산을 이용해
1. 큰 수를 작은 수로 나누는 나머지 연산을 수행한다.
2. 1번에서 작은 수를 큰 수로, 나머지 값을 작은 수로 하여 두 수를 다시 나머지 연산을 한다.
3. 이 과정을 반복해서 나머지가 0이 나오면 이 때 작은 수의 값이 최대 공약수가 된다.

이제 이렇게 구한 최대공약수를 이용해 최소공배수를 구할 수 있다.
최소공배수 = 최소값 * 최대값 / 최대공약수

여기서 한 풀이처럼 굳이 재귀함수를 사용하지 않아도 되지만, 재귀함수를 사용할 때마다 막히는 경향이 있어서 조금이라도 익숙해져보고자 재귀함수로 풀어봤다.