(C++) 백준 1934번 - 최소공배수

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

문제

> 두 자연수 A, B가 주어졌을 때 두 수의 최소공배수를 구해라.

접근

두 자연수의 최소공배수는 두 자연수의 곱 / 최대공약수로 구할 수 있다. 최소공약수는 유클리드 호제법을 사용하면 된다.
유클리드 호제법은 a,b에 대해 a를 b로 나눈 나머지를 r이라고하고 b를 r로 나눈 나머지를 r'로 한다면 이를 반복했을때 0이 나오는 경우의 나누는 수가 최대 공약수가 된다.

문제해결

> 유클리드 호제법 함수를 만든다. 두 수를 인수로 받아 나머지가 0일 때까지 a%b=r, b%r = r'를 반복한다. 
> 테스트 케이스만큼 while문을 돌며 입력받고 유클리드 호제법을 사용하고 출력한다.
> 항상 a가 b보다 클때를 가정하고 했기 때문에 b가 더 큰 경우를 고려해 그렇다면 a와 b를 swap해주고 연산한다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

int GCD(int a, int b)
{
	int r;
	while (b != 0)
	{
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

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

	while (t--)
	{
		cin >> a >> b;
		if (b > a)
			swap(a, b);

		cout << a * b / GCD(a, b) << '\n';
	}
}

후기

최소공배수, 최대공약수 문제가 자주 나오고 자주 쓰이는데 이럴때 유클리드 호제법을 사용하면 쉽게 할 수 있는걸 배웠다. 생각해보면 대학수학인지 이산수학인지 선형대수학인지 수업에서 gcd를 배웠던것 같다.