Beakjoon] 최소공배수 (백준 1934코테) - 정수론 (C++)

---

🅰️문제주소 : https://www.acmicpc.net/problem/1934

 

🚩문제 

 

 

🪡풀이 

 - 우선 유클리드 호제법으로 최대공약수를 구해야한다 
 - 최소공배수 = 'A*B / 최대공약수'  공식에 대입한다 끝

 

☕코드는 아래 숨김

#include <iostream>

int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(0);
	std::cin.tie(0);
	int T, A, B;

	std::cin >> T;

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

		int big, small;
		if (A <= B) {		//A가 B보다 작다는 표현이 명확하지 않아서 조건넣음
			big = B;
			small = A;
		}
		else {
			big = A;
			small = B;
		}

		while (small != 0) { //재귀 함수로 더 깔끔하게 구현가능
			int temp_mod = big % small;
			big = small;
			small = temp_mod;
		}
		std::cout << A * B / big << "\n";
	}
	return 0;
}

 

💡알게 된 것 

 - 유클리드 호제법
   1) A와 B의 최대공약수를 구하려면 큰수/작은수의 나머지값을 구한다
   2) '기존 작은수'가 '다음번 큰수'가 되고 '구했던 나머지 값'이 '다음번 작은수'가 된다.
   3) 나머지가 0이될때까지 반복해서 나머지가 0일때 '작은수' 값이 최대 공약수이다

- 최소 공배수는 'A*B/최대 공약수'

---