최소공배수

풀이 언어 : C언어

문제 링크 : 최소공배수

• 수학 문제긴 하나, 이러한 유형을 쉽게 풀려면 유클리드 호제법과 재귀함수를 알면 좋다.

#include <stdio.h>

int lcd (int a, int b)
{
	if (b==0)
	{
		return a;
	}
	
	else
	{
		return lcd (b,a%b);
	}
}


int main()
{
	int a,b,k,i;
	scanf("%d",&k);
	
	for (i=0; i<k; i++)
	{
		scanf("%d %d",&a,&b);
		int d = lcd(a,b);
		int e = d*(a/d*b/d);
		printf("%d\n",e);
	}
	
	return 0;
}

1. 최소공배수를 구할 함수를 정의하였습니다. 전달받을 두 변수 a,b를 갖고 계산을 했는데 b가 0이 아니라면 a와 b를 나눴을 때의 나머지값과 b값을 반환하도록 했습니다.

2. 즉, lcd (a,b)자리를 -> lcd(b,a%b)로 재귀시키면서 b가 0이 될 때까지를 구하는 중입니다.

예를 들어서 16,24를 입력했다 합시다.

그러면 (16,24) -> (24,16) -> (16,8) -> (8,0) -> 출력 값 8
즉, 16과 24의 최대공약수는 8입니다.

하지만, 문제에서 요구하는 것은 최소공배수이므로 조금 더 작업이 필요해요. 두 변수 a,b를 최대공약수로 나눠준 값들. 그리고 최대공약수를 모두 곱하면 그게 최소공배수가 되죠? 따라서 2,3,8을 다 곱하면 48이 최소공배수가 됩니다.

main함수의 코드는 그걸 나타내고 있습니다.

k는 테스트 케이스 개수를 의미합니다!