BOJ. 2609

#BOJ2609

최대공약수와 최소공배수

GCD 문제의 시작점으로 선택하기에 매우 좋다. 유클리드 호제법을 사용해서 풀 수 있는데 솔직히 범위가 좀 작고, 시간제한도 여유 있어서 하나한 확인하면서 최대공약수를 찾는 브루트 포스를 사용해도 괜찮아 보인다. 하지만 나는 게으르기 때문에 유클리드 호제법을 이용해서 GCD를 찾는 함수를 가져다가 쓸 것이다. 나무위키꺼를 참고해서 올린다.

int Euclidean(int a, int b)
{
    int r = a % b;
    if (r == 0) {
      return b;
    }
    return Euclidean(b, r);
}

보자마자 이 얼마나 날먹인지 감이 다들 오시는가 대소비교도 해줄 필요없이 그냥 GCD를 바로 리턴해준다. 이걸 이용해서 그냥 LCM은 곱셈 나눗셈만 해주면 된다.

# include "iostream"
using namespace std;

int Euclidean(int a, int b)
{
    int r = a % b;
    if (r == 0) {
      return b;
    }
    return Euclidean(b, r);
}

int main(void){
    int A, B, GCD = 0;
    cin >> A >> B;
    GCD = Euclidean(A, B);
    cout << GCD << endl;
    cout << A * B / GCD << endl;
}