[프로그래머스] Level1 - 최대공약수와 최소공배수

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

---

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한사항

• 두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

입출력 예 #1

위의 설명과 같습니다.

입출력 예 #2

자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

---

풀이

최대 공약수(Greatest Common Measure)와 최소 공배수(Least Common Multiple)을 각각 첫글자를 따서 G와 L로 표시한다.
두 자연수 A,B의 최대 공약수를 G, 최소 공배수를 L이라고 하면 아래와 같이 표시할 수 있다.
A = G x a
B = G x b
L = G x a x b (a,b는 서로소이다)
A x B = L x G(L = A x B / G)
우리는 두 자연수를 인자로 받기 때문에 G와 L 둘중에 하나만 구하면 다른 하나는 쉽게 구할 수 있다. 최소 공배수보다 최대 공약수를 구하는 것이 쉬우니 최대 공약수를 먼저 구해준다. 그리고 A x B / G 를 해주어 최소 공배수를 구해준다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    int max = n >= m ? n : m;
    int min = n > m ? m : n;
    int result1, result2;
    
    for(int i=1;i<=min;i++){
        if(max % i == 0 && min % i == 0) result1 = i;
    }
    
    result2 = n * m / result1;
    
    answer.push_back(result1);
    answer.push_back(result2);
    return answer;
}