2609 JAVA 최대공약수와 최소공배수

 

학교 1주차 수업시간에서 배웠던 recursion에 관한 기본적인 문제이다. while문을 사용해서 이 문제를 해결할 수 있지만, 재귀를 복습하기 위해서 recursion을 사용해서 문제를 풀어본다.

 

최대 공약수 : 두 자연수의 최대의 약수, 나눈 수 중에서 두 수가 공통으로 가지고 있는 최대의 공통 자연수를 일컫는다.

최소공배수 : 두 자연수의 최소의 배수, 두 수의 배수 중에서 공통적이면서 최소의 자연수를 일컫는다.

 

최소 공배수는 두 수를 곱한 것 중에서 최대 공약수를 나누면 값이 나온다.

 

그렇다면 이 문제에서 중요한 것은 최대 공약수를 구하는 것이다.

 

최대 공약수는 두 수를 나눈 나머지를 나눈 나머지를 나눈 나머지와 같은 형식으로 나누는 값이 0이 되기 이전까지 계산하여 그 때의 몫을 최대 공약수로 정한다. 

 

즉, 코드를 통해 설명하면 

// 시간 복잡도 O(n) -> 오래걸림
while(b!=0){
	int r = a%b; // a를 b로 나눈 값
    
    r = b; // r은 b 위치로
    b = a; // b는 a 위치로
}

 

시간 복잡도가 커지기 때문에 시간 복잡도를 줄일 수 있는 재귀를 사용한다.

 

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

public class Main {
	public static int GCD(int a, int b) {
		if(b == 0) return a; // while 문 처럼 b가 0이면 몫을 return
		return GCD(b, a%b); // 아니면 이를 계속해라
	}
    
	public static int LCM(int a, int b, int gcd) {
		return (a*b)/gcd;
	}
    
	public static void main(String[] args) {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		try {
			st = new StringTokenizer(bf.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			int gcd = GCD(a, b);
			int lcm = LCM(a, b, gcd);
			System.out.println(gcd);
			System.out.println(lcm);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}