프로그래머스(C++) - 최대공약수와 최소공배수

●문제

 

●간단한 설명

int n값, int m값 d

n과 m의 최대공약수(GCD)와 최소공배수(LCM)을 return

 

●내가 푼 방법

유클리드 호제법 사용

나머지가 0이 될때까지 계속 나누는것을 반복하면 그때의 n값이 최대공약수가 됨

원래n과 m값을 저장

유클리드 호제법으로 GCD를 구함

(n* m) / GCD 로 LCM을 구함

결과를 {GCD, LCM}형태로 return

abs(a, b)로 최소공배수를 구함

 

●알아야하는 개념 / 알게된 개념

유클리드 호제법의 사용

최소공배수를 구하는공식 = LCM(a, b) = abs(a * b) / GCD(a, b)

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int n, int m)
{
	int gcd;
	int lcd;

	int originN = n;
	int originM = m;

	while (m != 0)
	{
		int newR = n % m;
		n = m;
		m = newR;
	}
	gcd = n;
	lcd = abs(originN * originM) / gcd;
	return { gcd, lcd };
}