백준 2609번: 최대공약수와 최소공배수 (C++)

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

• 입력
  • 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
• 출력
  • 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

코드

#include <iostream>
using namespace std;

int GCD(int a, int b){
    if (b == 0){
        return a;
    }

    return GCD(b, a % b);
}

int main(void){
    int a, b;

    cin >> a >> b;

    int gcd = GCD(a, b);
    int lcm = a * b / gcd;

    cout << gcd << '\n';
    cout << lcm << '\n';

    return 0;
}

접근 및 풀이

최대공약수를 구하는 문제의 경우 유클리드 호제법을 이용하면 된다.

유클리드 호제법이란?
두 양의 정수 \(a, b (a > b)\)에 대하여 \(a = bq + r (0 <= r < b)\)라 하면, \(a, b\)의 최대공약수는 \(b, r\)의 최대공약수와 같다.

즉, \(gcd(a, b) = gcd(b, r)\) 이고, \(r = 0\)이라면, \(a, b\)의 최대공약수는 \(b\)가 된다.

결론은 a를 b로 나눈 다음 딱 떨어진다면 b가 최대공약수이고 그렇지 않으면 나머지 r로 다시 b를 나누는 것이다. 딱 떨어져 최대공약수가 나올 때까지 이 과정을 반복하면 되기 때문에 재귀함수를 이용했다.

또한 유클리드 호제법 중에 \(a > b\)라는 조건이 있는데, 코드로 작성할 땐 \(a % b\)는 \(a\)를 호출하기 때문에 재귀 과정에서 자연스럽게 큰 값이 \(a\)로, 작은 값이 \(b\)로 들어가기 때문에 굳이 swap 함수를 넣어주지 않아도 된다.

최소공배수를 구할 때는 위에서 구한 최대공약수를 이용하면 된다. 최소공배수와 최대공약수 사이에는 다음과 같은 관계가 성립한다.

\(lcm(a * b) * gcd(a, b) = a * b\)

따라서 최소공배수는 \(a\)와 \(b\)를 곱한 값에 최대공약수를 나누어주면 된다.