본문 바로가기
코딩과 알고리즘

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

728x90

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

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

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;
}

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

 

728x90
반응형