🖊️ 문제

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

🖊️ 풀이

진짜 이거 필수다,, 이거는 외워놓자

최대공약수 = 두 수의 공약수 중 최대
최소공배수 = 두 수의 공배수 중 최소

최대공약수 (GCD : Greatest Common Divisor)

두 수의 약수들을 구하고 겹치는걸 구해서 최대값을 구하면 너무 .. 에바잖아?

n > m이라는 가정 하에,

다음 n : 이전 m
다음 m : 이전 (n % m)

이걸 m == 0까지 반복한다. m== 0일 때 n값이 최대공약수!

이게 유클리드 호제법이다
제발 기억하자 엄청 쉽다 ㅠㅠ

유클리드 호제법

int GetGCD(int n, m) {
	if (m == 0) return n;
    else return GetGCD(m, n % m);
}

최소공배수 (LCM : Least Common Multiple)

두 수의 곱을 최대공약수로 나누면 된다!!
(n * m) / GCD(n, m)

🖊️ 코드

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int GetGCD(int n, int m) {
    if (m == 0) return n;
    else return GetGCD(m, n % m);
}

int GetLCM(int n, int m) {
    return (n * m) / GetGCD(n, m);
}

vector<int> solution(int n, int m) {
    vector<int> answer;
    
    if (n < m) {
        int temp = m;
        m = n;
        n = temp;
    }
    
    answer.emplace_back(GetGCD(n, m));
    answer.emplace_back(GetLCM(n, m));
    
    return answer;
}