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

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12940

내 풀이

최대 공약수를 구한 뒤 두 수의 곱에서 최대 공약수를 나누면 최소 공배수이다.

내 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    int num = 1;
    int n1 = n;
    int n2 = m;
    for(int i = 2; i <= min(n1,n2); i++)
    {
        if((n1%i == 0) && (n2%i == 0))
        {
            n1 /= i;
            n2 /= i;
            num *= i;
            i--;
        }
    }
    answer.push_back(num);
    answer.push_back((n*m)/num);
    
    return answer;
}

다른 사람의 풀이

#include<vector>
#include<iostream>
using namespace std;


int Euclidean(int a, int b)
{
    return b ? Euclidean(b, a%b) : a;
}

vector<int> gcdlcm(int a,int b)
{
    vector<int> answer;
    // 유클리드 호제법
  answer.push_back(Euclidean(a,b));

  answer.push_back(a*b / answer[0]);

    return answer;
}

int main()
{
    int a=3, b=12;
    vector<int> testAnswer = gcdlcm(a,b);

    cout<<testAnswer[0]<<" "<<testAnswer[1];
}

다른 사람의 풀이 해석

최대공약수를 구하는 알고리즘인 유클리드 호제법을 사용하였다.

// 재귀함수형
int Euclidean(int a, int b)
{
    int r = a % b;
    if (r == 0) {
      return b;
    }
    return Euclidean(b, r);
}
//숏 코딩 재귀함수
f(a,b){return b?f(b,a%b):a;}