[C++] 백준 1934: 최소공배수

문제

[C++] 백준 1934: 최소공배수 BRONZE 1
https://www.acmicpc.net/problem/1934

 

---

 

접근 방법

백준 1934번은 두 수의 최소공배수(LCM) 를 구하는 문제다.
최소공배수를 직접 구하기보다는, 다음 공식을 이용하면 훨씬 쉽게 해결할 수 있다.

LCM(a, b) = a × b ÷ GCD(a, b)

 

따라서 문제의 핵심은 최대공약수(GCD) 를 구하는 것이다.
최대공약수는 유클리드 호제법을 이용하면 효율적으로 구할 수 있다.

https://xeungcoding.tistory.com/106

유클리드 호제법 (euclidean-algorithm)

 

이번에는 두 가지 방식으로 구현했다.

 

1. 반복문을 이용한 유클리드 호제법

int at = max(a, b), bt = min(a, b);
while (bt != 0)
{
    int ret = at % bt;
    at = bt;
    bt = ret;
}

 

유클리드 호제법의 핵심은 아래 공식을 반복하는 것이다.

GCD(a, b) = GCD(b, a % b)

 

• 큰 수를 작은 수로 나눈 나머지를 구하고
• 그 작은 수와 나머지로 다시 계산
• 나머지가 0이 되는 순간의 값이 최대공약수

반복문이 끝나면 at이 최대공약수가 된다.

이후 최소공배수는 a * b / at 으로 계산한다.

 

2. 재귀를 이용한 유클리드 호제법

같은 원리를 재귀 함수로도 구현할 수 있다.

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

• a % b == 0이면 → b가 최대공약수
• 아니면 → GCD(b, a % b) 호출

재귀적으로 나머지가 0이 될 때까지 호출된다.

메인에서는 이렇게 사용했다.

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

반복문 방식과 원리는 동일하고, 코드가 더 간결해지는 장점이 있다.

 

 

구현 시 주의할 점

• 반드시 최대공약수를 먼저 구한 뒤 a * b / gcd 순서로 계산해야 한다.
• 두 수 중 어떤 것이 더 큰지 상관없이 유클리드 호제법은 정상 동작한다.

 

 

---

 

코드

반복문 이용

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

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

	int T = 0;
	cin >> T;

	for (int i = 0; i < T; i++)
	{
		int a = 0, b = 0;
		cin >> a >> b;

		int at = max(a, b), bt = min(a, b);
		while (bt != 0)
		{
			int ret = at % bt;
			at = bt;
			bt = ret;
		}
		cout << a * b / at << '\n';
	}
}

 

재귀 이용

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

int GCD(int a, int b)
{
	if (a % b == 0)
		return b;
	else
		return GCD(b, a % b);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T = 0;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		int a = 0, b = 0;
		cin >> a >> b;

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