[백준_2609번] 최대공약수와 최소공배수

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

2609번: 최대공약수와 최소공배수

[문제]

 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

 

[입력 조건]

 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

 

[코드]

import java.util.*;

/*
 * 최대공약수 GCD -> 유클리드 호제법
 * a와 b의 최대공약수를 (a,b)라고 할 때 (a,b)의 최대공약수는 (b,r)의 최대공약수와 같다. 여기서 r은 a를 b로 나눈 나머지를 의미한다.
 * 즉, GCD(a,b) = GCD(b,r) 
 * 예를 들어 GCD(581,322)일 때 r(나머지)=259이다. 즉, GCD(581,322)=GCD(322,259)이다.
 * 이를 반복하면 GCD(581,322) = GCD(322,259) = GCD(259 63) = GCD(63,7) = GCD(7,0) = 7 이 된다.
 */
public class BaekJoon_2609 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();
		
		int d=gcd(a,b); // 최대공약수
		
		System.out.println(d);
		System.out.println(a*b/d); // 최소공배수
	}
	
	// 최대 공약수 구하는 함수
	public static int gcd(int a, int b) {
		while(b!=0) {
			int r=a%b; // 나머지를 구해준다.
			
			// GCD(a,b) = GCD(b,r)이므로 변환
			a=b;
			b=r;
		}
		// 나머지가 0이 되면 a 자리에 있는 값이 최대 공약수
		return a;
	}
}

 

[고찰]

 이번 문제의 핵심은 최대공약수를 구하는 것이었다. 어떻게 최대공약수를 구하는 것인지는 알고 있었지만 유클리드 호제법이란 공식을 사용하여 구하는 방법은 처음 접해봤기 때문에 우선 어떤 알고리즘으로 동작하는지 다른 사람의 포스팅을 참고하였다. 

 검색해보니 알고리즘도 간단했고 구현 또한 쉬웠다. 앞으로 '최대공약수를 구하는 알고리즘으로는 유클리드 호제법을 사용한다.'란 것을 기억해둬야겠다.