[JAVA] 백준 1934 유클리드 호제법

 

 

 

문제

두 수가 주어졌을 때 최소 공배수를 구하여라.

풀이

이 문제는 최소 공약수로 최대 공배수를 구하는 공식을 사용하여 풀었습니다.

위의 공식으로 해결할 수 있습니다.

최대 공약수, gcd()

    private static int gcd(int a, int b){
        if(a % b == 0)
            return b;
        else{
            return gcd(b, a%b);
        }

    }

유클리드 호제법을 사용하여 재귀 함수로 만들었습니다.

a % b = c

b % c = d

… 를 반복하여 나머지가 0이나왔을 때 b가 최소 공약수가 됩니다.

전체 코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append((a * b) / gcd(a, b)).append("\n");
        }
        System.out.println(sb);
    }

    private static int gcd(int a, int b){
        if(a % b == 0)
            return b;
        else{
            return gcd(b, a%b);
        }

    }

}

결과