[백준] 2609. 최대공약수와 최소공배수

: solved.ac class 2 - silver 5

 

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

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

 

 

예제 입력

24 18

예제 출력

6
72

 

정답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int eu_al(int a, int b)
{
	if (b == 0)
		return a;
	else
		return eu_al(b, a % b);
}

int main()
{
	int a, b, tmp, mul, div;

	scanf("%d %d", &a, &b);

	if (a < b) {
		tmp = b;
		b = a;
		a = tmp;
	}

    div = eu_al(a, b);
	mul = (a * b) / eu_al(a, b);

	printf("%d\n%d\n", div, mul);

	return 0;
}

---

해설

 

: 유클리드 호제법(Euclidean algorithm)을 이용한다.

 

보통 최대공약수와 최소공배수 문제는 for문 등으로 계속해서 나눠가는 방식을 택하는데, 구글링해 보니 최소공약수를 구하는 신기한 방식이 있어서 풀이에 한번 채택해 보았다.

골자는 이러하다. '최대공약수는 두 수를 공통되게 나눌 수 있는 가장 큰 수이다 -> 그러면 두 수 중 큰 수를 작은 수로 나누어서, 나머지가 생긴다면 그 나머지로 두 수를 나눌 수 있는지 확인해보면 어떨까?'

 

예시를 보면 어느 정도 감이 올 것이다. 큰 수는 작은 수들의 곱과 합으로 쪼갤 수 있다는 발상에서 착안한 방법인데,

큰 수를 작은 수의 곱과 나머지로 나타내고 -> 작은 수를 나머지의 곱과 또 그 나머지로 나타내고 -> ... 의 반복이다.

같은 과정을 대상만 바꾸어 계속 반복한다. 즉, 재귀로 쉽게 구현할 수 있다.

 

 

 

과정을 보자면 이러하다. 먼저 최대공약수/최소공배수를 구할 두 수를 입력받은 뒤,

크기를 비교하여 a에는 큰 수가, b에는 작은 수가 오도록 한다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	int a, b, tmp, mul, div;

	scanf("%d %d", &a, &b);

	if (a < b) {
		tmp = b;
		b = a;
		a = tmp;
	}
	//a가 b보다 작을 경우 swap해서
	//a에는 큰 수, b에는 작은 수가 오도록 하기

 

최대공약수를 구하는 것은 eu_al이라는 재귀함수로 나타냈다.

최소공배수는 두 수의 곱을 최대공약수로 나눈 값이므로, 이에 맞게 구현해주면 된다.

	div = eu_al(a, b);
	//최대공약수
	mul = (a * b) / eu_al(a, b);
	//최소공배수
	//(최소공배수는 두 수의 곱을 최대공약수로 나눈 값)

	printf("%d\n%d\n", div, mul);

	return 0;
}

 

eu_al 함수의 내용은 이러하다. 이해만 하면 구현은 정말 간단하다.

큰 수를 작은 수의 곱과 나머지로 나타내고 -> 작은 수를 나머지의 곱과 또 그 나머지로 나타내고 -> ... 의 과정을 반복하고

나머지가 0이 되는 시점이 오면 그 시점의 피젯수가 바로 최대공약수이다.

//유클리드 호제법으로 최대공약수를 구하는 함수 (재귀함수화)
int eu_al(int a, int b)
{
	if (b == 0)
		return a;
	else
		return eu_al(b, a % b);
}