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

1. 문제 이해

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 구하는 문제이다.

2. 문제 해결

이 문제를 본 나는 고민에 빠졌다.

최대공약수와 최소공배수를 수학책이나 문제집에서 나오게 되면

이와 같이 간단히 풀 수 있지만 이를 어떻게 코드로 옮길까 고민을 했다.

 

허나 이 고민은 백준의 알고리즘 분류를 보며 해결할 수 있었다.

이 문제의 알고리즘 분류는

이렇게 3가지가 있었다.

 

이 3가지 중 유클리드 호제법이라는 것을 몰랐고 이에 궁금증이 생겨 검색을 해봤다.

 

유클리드 호제법이란 두 자연수의 최대공약수를 구하는 알고리즘 중 하나였다.

그리하여 나는 이 알고리즘을 이용하여 최대공약수를 구하고

두 수의 곱 / 두 수의 최대공약수 = 최소공배수

라는 식을 이용해서 최소공배수 또한 구해주었다. 

3. 소스코드

#include<iostream>
#include<math.h>

using namespace std;

int main()
{
	int num1, num2, mainNum, remain;
	cin >> num1 >> num2;
	mainNum = max(num1,num2);
	remain = min(num1,num2);
	while (mainNum % remain != 0)
	{
		int temp = mainNum;
		mainNum = remain;
		remain = temp % remain;
	}
	cout << remain << endl << (num1 * num2) / remain;
}

---

유클리드 호제법이라는 새로운 알고리즘을 알게되었다!