[java] 백준 13241 최소공배수 자바

 

이 풀이는 유클리드 호제법을 사용하여 최대공약수와 최소공배수를 구하는 문제이다.

 

유클리드 호제법이란 최대공약수를 구하는 공식이다.

 

 

 

위와 같이 a, b가 있을 때 b가  0이 될 때 까지 재귀함수로 돌린다는 것을 알 수 있다.

 

위 공식을 통해 입력받은 값의 최대공약수를 구할 수 있다.

 

그렇다면 최소공배수는 어떻게 구하는가?

 

최소공배수는  a * b / gcd(a, b)로 계산할 수 있다.

 

 코드로 풀어보면 다음과 같다.

 

 

import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        long A = Integer.parseInt(st.nextToken());
        long B = Integer.parseInt(st.nextToken());

        System.out.print(A * B / gcd(A, B));
        // 최소공배수를 구하기 위한 공식

        br.close();

    }

    public static long gcd(long a, long b) {

        long r = a % b;
        // 두 수를 나눈 나머지

        if (r == 0) {
            return b;
            // r이 0이 될 때 까지 나누고, 0이라면 b가 정답이다.

        } else {
            return gcd(b, r);
            // 재귀함수로 b, r을 넣어 다시 gcd를 돌린다.

        }

    }

}