백준 2609번: 최대공약수와 최소공배수(C++)

www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

코드

#include <iostream>
using namespace std;

//최대공약수
int GCD(int n, int m){
	if(n % m == 0) return m;
	return GCD(m, n % m);}

int main() {
	int n, m; cin >> n >> m;
	cout << GCD(n, m) << endl << n * m / GCD(n, m);
}

 

풀이

정직한 제목에 정직한 풀이입니다.

최대공약수를 구하고 최소공배수를 구하면 됩니다. 물론 이 둘을 구하는 방법에는 다양한 방법이 있겠지만

저 같은 경우에는 유클리드 호제법을 사용했습니다.

ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

자세한 알고리즘에 대한 설명은 위키를 참고 해 주시길 바랍니다. 

크게 어려운 알고리즘은 아닙니다. 두 수가 서로를 나누어서 최대공약수를 구하는 방법인데요,

 

어찌됐든 유클리드 호제법을 사용해서 최대공약수를 구한다면 이를 통해 최소공배수도 바로 구할 수 있습니다.

 

최소 공약수는 두 수의 곱을 최대공약수로 나눈 값입니다.

따라서 위의 코드와 같이 최대공약수를 구하는 함수를 작성하시면 최소공약수는 바로 구할 수 있습니다.