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

<문제 소개>

---

<소스 코드>

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <unordered_map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

int main()
{
	// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;

	vector<int> v;
	
	for (int i = 0; i < T; i++)
	{
		int A, B;
		cin >> A >> B;
		
		int small = A > B ? B : A;
		int big = A == small ? B : A;

		int k = 1;
		int minVal = small; // 최소공배수를 저장할 값

		while (true)
		{
			if (minVal % big == 0) break;

			minVal = small * ++k;
		}

		v.push_back(minVal);
	}

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << "\n";
	}

	return 0;
}

---

<풀이과정>

1. T를 입력받고, 벡터 v를 선언

2. T만큼 반복하며 A, B를 입력받고 A와 B를 비교해 작은 수와 큰 수를 찾는다.

3. 작은 값에 1부터 차례로 곱하고, 해당 수를 큰 수로 나누었을 때 나누어 떨어지는 지점이 최소공배수이다.

4. 그러므로 곱해지는 수 k를 1로 선언, 곱해져서 나오는 값을 저장할 minVal를 small로 선언한다.

5. 이후 while문을 이용해 minVal에 k를 곱하는 과정을 반복하면서 minVal를 big으로 나누어 떨어지는 경우에 break 시키고, 최소공배수에 해당하는 minVal를 벡터 v에 넣어준다.

6. v의 원소들을 출력해준다.

---

<코멘트>

이렇게 푸는게 맞는지 싶어서 다른 풀이를 찾아보았다.

보통은 유클리드 호제법을 사용해 푸는 것 같았다.(사실 예전에 공부했었는데 까먹었음..ㅋㅋ)

근데 내가 생각해낸 방법이 유클리드 호제법이랑 거의 흡사한 것 같다.(아닌가?)

 

<유클리드 호제법>

- 최대공약수를 구하는 알고리즘

- 2개의 자연수 a, b에 대해 a를 b로 나눈 나머지를 r이라고 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

- 이를 이용해 b를 r로 나눈 나머지 r'을 구하고 다시 r을 r'으로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때, 나누는 수가 a와 b의 최대공약수이다.

- 최소공배수는 최대공약수를 구한 뒤 [a x b / 최대공약수]의 공식으로 구할 수 있다.

// 예시) 78696, 19332의 최대공약수 구하기
78696 ＝ 19332×4 ＋ 1368
19332 ＝ 1368×14 ＋ 180
1368 ＝ 180×7 ＋ 108
180 ＝ 108×1 ＋ 72
108 ＝ 72×1 ＋ 36
72 ＝ 36×2 ＋ 0

---

<제출결과>