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

문제 링크 : https://www.acmicpc.net/problem/2609

참고한 블로그 : https://coding-factory.tistory.com/599

말 그대로 두 수가 주어질 때 최대공약수와 최소공배수를 구하는 문제이다. 분명 구하는 공식이 따로 있었는데 생각이 나질 않아서 검색해서 풀었다.

유클리드 알고리즘(Euclidean algorithm)은 2개의 자연수의 최대공약수를 구하는 알고리즘입니다. 비교대상의 두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다."라는 원리를 활용한 알고리즘입니다. (위 참고한 블로그에서 인용)

알고리즘 수업시간에 배웠는데, 분명 시험 문제로도 풀었는데... 그만큼 공부를 하지 않았다는 뜻이겠지. 아무튼 위 공식을 이용하면 바로 풀 수 있다.

<작성한 코드>

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a, int b){
    if(b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int main()
{
    int a[2];
    cin >> a[0] >> a[1];
    sort(a, a + 2);
    
    int n = gcd(a[1], a[0]);
    cout << n << endl << a[0] * a[1] / n;
}

gcd(a, b)에서 a > b여야 한다고 해서 그냥 크기 2짜리 배열로 선언해두고 sort로 정렬해서 바로 넣었다. 아니면 a, b로 따로 받은 후 max나 min 함수로 크기 비교를 해서 큰 숫자를 먼저 넣는 방식으로 할 듯?
꼭 기억하자 유클리드 호제법