[프로그래머스/C++] Lv.1 최대공약수와 최소공배수

문제

문제

---

코드

#include <string>
#include <vector>

using namespace std;

// 최대공약수
int gcd(int a, int b)
{
	if(b == 0) return a;
    return gcd(b, a%b);
}

// 최소공배수
int lcm(int a, int b)
{
	return a*b/gcd(a,b);
}

vector<int> solution(int n, int m) {
    vector<int> answer;
    answer.emplace_back(gcd(n,m));
    answer.emplace_back(lcm(n,m));
    return answer;
}

// 또는
int lcm(int a, int b)
{
    return a*b/__gcd(a,b);
}

vector<int> solution(int n, int m) {
    vector<int> answer;
    answer.emplace_back(__gcd(n,m));
    answer.emplace_back(lcm(n,m));
    return answer;
}

---

문제 해설

- 유클리드 호제법을 사용한다.
함수안에서 b가 0이 될 때까지 a를 b로 나눈 나머지를 b에 대입하면서 최대 공약수를 구한다.
재귀함수를 통해 최대공약수를 구할 수 있다.
또는 C++ STL의 __gcd() 함수를 이용해 최대 공약수를 구할 수 있다.

- 최대공배수
최대공약수를 구할 수 있으면 최대 공배수도 쉽게 구할 수 있다.
a * b = gcd(a,b) * lcm(a,b)


// 참고
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=kmc7468&logNo=221017936040
https://wyatti.tistory.com/entry/Cc-%EC%B5%9C%EB%8C%80-%EA%B3%B5%EC%95%BD%EC%88%98