2609 - 최대공약수와 최소공배수

• 난이도: 브론즈 1
• 날짜: 2023년 2월 5일
• 상태: Correct
• 추가 검토 여부: Yes

solution

• 최대공약수, 최소공배수 알고리즘을 묻는 문제였다.
• 최대공약수, 최소공배수 모두 유클리드 호제법을 사용하여 알고리즘을 구현할 수 있다.
• 유클리드 호제법 알고리즘을 깜빡해서 검색을 했다.
  • 유클리드 호제법은 두 수중 작은 수로 큰 수를 나눈 나머지와 작은 수의 최대공약수를 재귀적으로 구하는 알고리즘이다. 나머지 값이 0이 될때까지 반복한다.
  • 최소공배수는 두 수의 곱을 최대공약수로 나눈 값이다.

code

#include <iostream>

using namespace std;

int gcd(int a, int b)
{
    int tmp;
    if(a < b) 
    {
        tmp = a;
        a = b;
        b = tmp;
    }
    int n;
    while(b != 0)
    {
        n = a % b;
        a = b;
        b = n;
    }
    return a;
}

int lcm(int a, int b)
{
    return (a*b) / gcd(a, b);
}

int main()
{
    int a, b;
    cin >> a;
    cin >> b;

    cout << gcd(a, b) << endl;
    cout << lcm(a, b) << endl;

    return 0;
}

ref

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