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

1. 문제이해

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

1934번: 최소공배수

 

테스트 케이스의 개수와 테스트 케이스의 개수만큼 두 자연수 A, B가 주어질 때,

A, B의 최소공배수를 출력하는 프로그램을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

T개의 A와 B를 입력받아, 각각의 최소공배수를 출력하는 것이 목표이다.

이전 포스팅에서 두 수의 최대공약수와 최소공배수를 구하는 문제를 풀이한 적이 있었는데,이 문제에도 해당 문제와 동일한 알고리즘을 이용해 풀이해주었다.

 

자세한 내용은 아래 포스팅을 참고하자.

https://beginnerdeveloper-lit.tistory.com/2

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

 

위 포스팅에서와 동일하게, a x b = 최대공약수 x 최소공배수 라는 공식을 이용해

최소공배수 = a x b / 최대공약수 를 도출.

해당 식을 이용해 최소공배수를 구해주기로 했다.

 

위와 같은 식을 이용해 최소공배수를 구하기 위해서는 최대공약수 또한 필요한데,

최대공약수는 유클리드 호제법을 이용해 구해주기로 했다.

(유클리드 호제법이란, 두 정수 a, b에 대해, a를 b로 나눈 나머지인 r을 이용해,

최종적인 나머지가 0이 될때까지 위의 과정을 반복하는 것이다.

자세한 내용은 위의 포스팅을 참조하자.)

 

 

 

3. 소스코드

#include <iostream>
using namespace std;

// 최대공약수를 구하는 함수 (유클리드 호제법 이용)
int gcd(int a, int b) {
	int r = a % b;
	if (r == 0) {
		return b;
	}
	else {
		return gcd(b, r);
	}
	
}

int main() {
	int T;        // 테스트 케이스의 개수
	int A, B;
	int lcd;      // 최소공배수

	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> A >> B;

		// 최소공배수 = (A x B) / 최대공약수
		lcd = (A * B) / (gcd(A, B));
		cout << lcd << "\n";
	}

	return 0;
}

먼저, 두 수의 최대공약수를 구하는 함수인 gcd 함수를 선언해주었다.

해당 함수는 유클리드 호제법을 이용한 알고리즘으로 구현해주었는데,

두 정수 a, b에 대해, a를 b로 나눈 나머지인 r을 이용, 나머지가 0이 될때까지 위의 과정을 반복했다.

 

메인함수에서는 테스트 케이스의 개수(T)를 입력받고,

테스트 케이스의 개수만큼 최소공배수를 구하는 과정을 반복해주었다.

최소공배수는, A와 B를 입력받은 다음, 최소공배수 = a x b / 최대공약수 라는 식과

위에서 정의한 gcd 함수를 통해 도출한 최대공약수를 이용해 구해주었다.

 

 

---

최대공약수를 구하는 알고리즘과 최소공배수를 구하는 식을 이해했다면 쉽게 풀이할 수 있는 문제였다.

필자는 예전에 푼 문제를 기반으로 금방 풀이했다.🤭

문제에 대한 지적이나 질문은 언제나 환영입니다.😌