백준 13241 최소 공배수 With JAVA

 

 

 

https://www.acmicpc.net/problem/13241

13241번: 최소공배수

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_S3_13241 {
    static long n;
    static long m;
    static long result;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Long.parseLong(st.nextToken());
        m = Long.parseLong(st.nextToken());
        
        System.out.println(lcm(n, m));
    }
    
    // 최대 공약수
    public static long gcd(long a, long b) {
        while (b > 0) {
            long temp = a;
            a = b;
            b = temp % b;
        }
        
        return a;
    }
 
    // 최소 공배수 => (a * b) / a와 b의 최대 공약수
    public static long lcm(long a, long b) {
        return (a * b) / gcd(a, b);
    }
}

 

먼저 버퍼리더와 토크나이저 하나를 만들어 준다. 그 다음 첫 번째수 n과 두 번째 수 m을 만들어 주고 lcm 함수를 호출해 준다 lcm 함수는 최소공배수를 알려주는 함수이다. 이 함수를 알아보기 전에 먼저 최대 공약수를 만드는 알고리즘을 설계 해주어야 한다. 왜냐면 최소 공배수를 알려면 최대 공약수를 아는 것이 먼저이기 때문이다. 최대 공약수 알고리즘은 유클리드 알고리즘을 사용했다. 이 알고리즘을 사용하면 두 수의 최대 공약수를 알 수 있다. 그 다음 최소 공배수의 성질은 최소 공배수는 두 수의 곱을 최대 공약수로 나눈 값으로 계산된다는 것이다. 예를 들어 a = 12, b = 18인 경우를 생각해보자. 이 경우 gcd 값 : 최대 공약수는 6이다. 12 * 18 / 6 (최대공약수) 를 하면 최소 공배수는 36이 된다. 이렇게  최소 공배수를 구하는 것이다. 이 성질을 이용하여 코드를 구현하면 위와 같다.