[백준/C++]#2609 - 최대공약수와 최소공배수

풀이

#define min(a,b) (((a)<(b)) ? ((a) : (b)))
#include <iostream>
using namespace std;

int gcd(int x, int y) {
	int r;
	for (int i=1; i<=min(x,y); i++) {	//1부터 x,y 중 가장 작은 값까지 반복함
		if (x%i==0 && y%i==0)	// x,y 둘 다 i로 나눠지는 경우
			r = i;		// 그때의 값을 저장
	}
	return r;
}

int main() {
	int a,b;
	cin >> a >> b;
	int gc = gcd(a,b);	// 최대공약수 gc
	int lc = (a/gc)*(b/gc)*gc;	// 최소공약수 lc
	cout << gc << '\n' << lc;
	return 0;
}

개념

이번엔 수학 카테고리 문제이다.

최대공약수와 최소공배수는 가물가물한데, 아래 그림을 보자.

서로수가 될 때까지 나눈 뒤, 나눈 값(6)은 최대공약수이고 6 X 4 X 3은 최소공배수이다.

---

풀이 

최대공약수를 구하면, 그 값을 통해 최소공배수를 구하기는 쉽다.

따라서 최대공약수를 구하는게 관건인데, 따로 함수를 만들었다.

 

최대공약수는 a와 b 모두에게서 나머지가 없이 나눠져야한다.

경우에 따라서 a, b 중 작은 값과 같아질 수도 있다. (ex. 5, 10의 최대공약수)

따라서 두 값 중 작은 값까지 반복되는 for문을 사용했다.

a, b 모두에게 나눠지는 경우를 if문으로 짜면, '최대' 공약수이므로 i값이 증가함에 따라 알아서 최대값이 저장된다.

 

최소공배수는 최대공약수가 r이라면 r * (a/r) * (b/r) 이다.

 

---

+a

문제에서 최솟값을 구하는 매크로 함수의 경우 맨 위에 안써주면 컴파일 오류가 작동한다.

 

그리고 최댓값의 경우 다른 방식으로도 구할 수 있다.

이 방식은 값(a, b)이 커질 때 반복을 줄이는 이점이 있다.

유클리드 호제법을 사용하는 것이다.

이는 r이 최대공약수일 때 gcd(a,b) = gcd(b,r) 이고, r=0이 될 때 a,b의 최대공약수는 b라는 알고리즘이다.

int gcd(int x, int y) {
	if (y == 0) return x;
	return gcd(y, x%y);
}

x,y에 16,24가 들어오든 24,16이 들어오든 문제없이 작동한다. 들어오는 수의 크기 순서에 상관이 없는 알고리즘이다.