[JAVA] 백준 2609 - 최대공약수와 최소공배수(유클리드 호제법)

문제 풀이 전 이론 - 1

- 최대공약수는 줄여서 GCD라고 한다.

- 두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다.

- 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A,B)까지 모든 정수로 나누어 보는 방법이 있다.

- min(A,B)인 이유는 어차피 두 수의 공통된 약수 중 가장 큰 정수는 min(A,B)보다 크지 않기 때문이다.

- 위의 이론은 O(N)이고, 입력이 10,000이하이기 때문에 시간 제한 1초 내에는 충분히 실행가능하다.

- 하지만 이보다 더 빠른 방법으로 문제를 해결하기 위해 유클리드 호제법]을 사용해본다.

int g =1;
for(int i = 2; i <= min(a,b); i++){
	if(a%i == 0 && b%i == 0){
    	g = i;
    }
}

문제 풀이 

- a를 b로 나눈 나머지를 r이라고 했을 때

- GCD(a,b) = GCD(b,r)과 같다.

- r이 0이되면 그 때 b가 최대공약수이다.

- 코드로 구할 때는 r이 0이 될 때까지 재귀함수를 호출하여 해결할 수 있다.

- 최소공배수는 LCM라고 한다.

- a를 최대공약수로 나누었을 때의 몫, b를 최대공약수로 나누었을 때의 몫을 구한 후

- 최대공약수에 곱해주면 된다.

- G x (a/G) x (b/G) = 최소공배수

 

소스 코드

public class Main {
	public static void main(String[] args) {
		int a,b,r,min,maxres = 0,minres = 0;
		Scanner scan = new Scanner(System.in);
		
		a = scan.nextInt();
		b = scan.nextInt();
		
		maxres = GCD(a,b);
		minres = LCM(a,b,maxres);
		
		System.out.println(maxres);
		System.out.println(minres);
	}
	
	public static int GCD(int a,int b) { 
		if(b == 0) {
			return a;
		}else {
			return GCD(b,a%b); 
		}
	}
	
	public static int LCM(int a,int b, int gcd) {
		return gcd * a/gcd * b/gcd;
	}
}

출력

문제로부터 얻어간 것

이 문제는 유클리드 호제법을 사용하지 않아도 충분히 풀 수 있었지만, 입력 값을 더 크게 받음으로 인해서 실행시간이 초과되는 경우에 사용할 수도 있어 매우 편리하다고 생각한다. 코드도, 이론도 어렵지 않기 때문에 더욱 유용하다.