[알고리즘 스터디] 1주차_재귀함수_Ex018

입력된 두 수의 최소 공배수를 구하고, 전개도 작성하기

#include <iostream>
#include "Practice.h"

int lcm(int a, int b)
{
	if (a < b)
	{
		lcm(b, a);
	}
	else
	{
		if (a % b != 0)
		{
			lcm((a % b), b);
		}
		else
		{
			return b;
		}
	}
}

void Recursive(int a, int b)
{
	std:: cout << (a / lcm(a, b)) * (b / lcm(a, b)) * lcm(a, b);
}

int main(void)
{
    Recursive(10, 6);
    
    return 0;
}

// 전개도

R(10, 6)
{
	lcm(10, 6)
	{
		if(false)
		if(true)
		{
			lcm(4, 6)
			{
				if(true)
				{
					lcm(6, 4)
					{
						if(false)
						if(true)
						{
							lcm(2, 4)
							{
								if(true)
								lcm(4, 2)
								{
									if(false)
									if (true)
									{
										return 2;
									}
								}
							}
						}
					}
				}
			}
		}
	}

	gcd = 2;

	cout(5 * 3 * 2);
}

<실행 결과>

결론

---

a와 b의 최대 공약수 c를 구한다.
최소공배수(lcm) = (a / c) * (b / c) * c