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

programmers.co.kr/learn/courses/30/lessons/12940

코딩테스트 연습 - 최대공약수와 최소공배수

 

풀이

유클리드 알고리즘을 이용하여 두 수의 최대 공약수와 최소 공배수를 구하는 문제이다.

유클리드 알고리즘이란 a=12, b=18이라고 할 때, b를 a로 나눈 나머지가 0이면 a가 최대 공약수가 되고, 만약 0이 아니라면 b의 값을 a로, b%a의 값을 b로 두어 이를 나눈 나머지가 0인지 계속 확인하는 것이다.

이렇게 최대 공약수를 구하고 난 후, 최소 공배수는 (최대 공약수 * a/최대 공약수 * b/최대 공약수) 식을 통해 쉽게 구할 수 있다.

 

백준에도 똑같은 문제가 있으므로 이것도 풀어보면서 알고리즘에 익숙해지면 좋을 것 같다.

www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

전체 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    if(n<m) swap(n,m);
    int i=n, j=m;
    while(1) {
        if(i%j==0) {
            answer.push_back(j);
            break;
        } else {
            int tmp=i;
            i=j;
            j=tmp%j;
        }
    }
    int x=answer[0]*(n/answer[0])*(m/answer[0]);
    answer.push_back(x);
    return answer;
}