백준 알고리즘 1934번. 최소공배수

초등학교 산수(요새 말로는 수학) 시간에 "최소공배수"를 구해본 기억이 있으신가요?

기억이 가물가물한 분들이 더욱 많을듯 해서 다시 상기시켜드립니다.

​

2개의 수의 배수중 가장 작은 수가 바로 최소공배수입니다.

이를 테면 12과 20의 배수이면서 그중 가장 작은 배수는

12x20=240이 아니라, 60인 것이지요.

60이란 숫자는 12의 배수인 동시에 20의 배수이기도 합니다.

​

이런 최소공배수를 구하는 방법이 있습니다.

알고리즘 풀이로 널리 알려진 유클리드 호제법이란 방법도 있지만,

크레이는 그냥 클래식한 방법으로 설명 및 풀이를 진행하도록 하겠습니다.

​

수학 시간의 배운 내용을 그대로 펼쳐볼까요?

맨 처음 2개의 숫자를 나란히 씁니다.

 

두 수를 동시에 나눌수 있는 숫자를 왼쪽에 적어줍니다.

그리고 그 나눈 결과를 아래에 씁니다.

아래에 적은 2개의 수를 또 두나눌수 있는 숫자가 있다면 왼쪽에 또 적은 다음,

나눈 결과를 또 아래에 기재합니다.

더 이상 나눌 수 없을 때가 되었다면,

왼쪽에 적은 모든 숫자 ( 2, 2 ) 와 아래에 남아 있는 2개의 숫자 ( 3, 5 ) 를 모두 곱한 것이 바로 최소공배수가 됩니다.

 

 

아래 소스는 이번 문제를 이 클래식한 방법으로 풀이한 소스입니다.

​

유클리드 호제법은 너무 많이 널려 있어서, 크레이는 좀 색다르게 보이려고(?) 이 방법으로 진행했는데, 주석을 좀 많이 달아 놓았으니 궁금한 부분 있으면 문의주시면 가능한 선에서 답변 드리겠습니다.

 

#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

// 유클리드 호제법이 아닌 크레이의 클래식한 방법
// 장점 : 두 수의 약수 목록과 최종산출결과도 추출할 수 있습니다.
// 약간만 개조하면 3개이상의 수의 최소공배수도 쉽게 구할 수 있습니다.
vector<int> GCD(long A, long B, long *ResultA, long *ResultB, long *gcd)
{
	vector<int> aliquot;	//  약수목록

	// 최소공배수를 곱하기 위한 기본수치를 1로 정합니다.
	*gcd=1;			

	// 2부터 진행합니다.
	for(long i=2;i<=A;++i)
	{
		// A, B 모두 나누어 떨어지는 숫자인지 검사합니다.
		while(A%i==0 && B%i==0 && A>=i && B>=i)
		{	
			// 아래 주석을 풀면 실제 풀이 과정을 볼 수 있어요!
			//printf(" %6ld | %6ld %6ld\n", i, A, B);
			//printf("        +-----------------\n");

			// A와 B 를 각각 나누어줍니다.
			A /= i; 
			B /= i;
			*gcd *= i;	// 최소공배수에 나눈 숫자를 곱합니다.
			aliquot.push_back(i);	// 약수 목록도 추가해줍니다.
		}
	}
	// 아래 주석을 풀면 실제 풀이 과정을 볼 수 있어요!
	//printf("          %6ld %6ld\n", A, B);

	// 앞의 약수 목록에 최종 A, B 를 곱하면 최소공배수가 됩니다.
	*ResultA=A; *gcd *= A;
	*ResultB=B; *gcd *= B;

	// 아래 주석을 풀면 실제 풀이 과정을 볼 수 있어요!
	//printf("          GCD = %ld\n\n", *gcd);	

	// 약수 목록을 반환합니다
	return aliquot;
}

void Result()
{
	int t;
	// 테스트 케이스 입력
	scanf("%d", &t);
	// 테스트 케이스 반복
	while(t--)
	{
		// 입력받을 A, B, 최종적으로 구해질 아래쪽 수치 A, B, 그리고 gcd 변수를 담을 공간까지 모두 정의합니다.
		long A, B, ResultA, ResultB, gcd;
		// A B 를 입력받습니다.
		scanf("%ld %ld", &A, &B);
		// 최소공배수를 산출합니다. 벡터변수 aliquot 는 2 수의 약수 목록입니다.
		vector<int> aliquot = GCD(A, B, &ResultA, &ResultB, &gcd);
		printf("%ld\n", gcd);
	}
}

int main()
{
	Result();
	getchar(); getchar();
	return 0;
}

참고로 소스내에 주석을 풀어주시면 아래와 같이 계산식을 직접 보실 수도 있습니다 :)