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

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

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

사고과정1)

브루트포스 알고리즘, 즉 모든 경우의 수를 다 생각해서 코딩했다.

입력 받은 두 수가 같으면, 최대공약수와 최소공배수는 한 수일 것이고

만약 두 수가 서로소라면, 최대공약수는 1이고 최소공배수는 두 수의 곱인 경우를 따로 조건문으로 처리했다.

#include <iostream>
using namespace std;

int main()
{
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	int a, b;
	cin >> a >> b;

	if (a == b)
	{
		cout << a << '\n';
		cout << a;
		return 0;
	}
	int small = a > b ? b : a;
	int big = a < b ? b : a;


	int index = 0;
	for (int i = 1; i <= small; i++)
	{
		if (small % i == 0 && big % i == 0)
			index = i;
		if (i == small && index == 0)
		{
			cout << 1 << '\n';
			cout << small * big;
			return 0;
		}
	}
	cout << index << '\n';
	int div_small = small / index;
	int div_big = big / index;

	cout << (long long)index * div_small * div_big;

	return 0;
}

다만 뭔가 아쉬워서, 다른 방법이 없나 찾아봤더니 

'유클리드 호제법' 이라는 이런 공약수 공배수 사용하는 문제에 자주 사용되는 알고리즘이 있어서 가져와봤다.

 

1. 큰 수를 작은 숫자로 나머지 연산 처리한다.

2. 작은 숫자로 1번에서 구한 나머지를 나머지 연산 처리한다. 

3. 결과가 0이 될때까지 반복

4. 나누는 수로 사용된 수가 최대공약수가 된다.

ex)

1428 % 833 = 595

833 % 595 = 238

595 % 238 = 119

238 % 119 = 0

 

이므로 119가 최대공약수고 최소공배수는 최대공약수 * (a / 최대공약수) * (b / 최대공약수)