[백준] 5347_LCM C++

04 Nov 2023 in Study on Coding Test

유클리드 호제법을 기억하기 위한 문제

정답제출코드

#include <iostream>

using namespace std;

long long GCD(int big, int small)
{
    if (big % small == 0)
        return small;
    return GCD(small, big % small);
}

long long LCM(int a, int b)
{
    long long big, small;
    if (a >= b)
    {
        big = a;
        small = b;
    }
    else
    {
        big = b;
        small = a;
    }
    long long Gcd = GCD(big, small);
    return (big * small) / Gcd;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int N;
    cin >> N;
    
    for (int i = 0; i < N; ++i)
    {
        int a, b;
        cin >> a >> b;

        cout << LCM(a, b) << '\n';
    }
    
    return 0;
}

실버 5 급으로 비교적 쉬운 문제이지만

유클리드 호제법에 대한 내용을 자꾸 까먹어서 기록을 남기고자 풀고 포스팅을 한다.

여기서 GCD(최대공약수)를 구하는 유클리드 호제법 구간은 아래와 같다.

long long GCD(int big, int small)
{
    if (big % small == 0)
        return small;
    return GCD(small, big % small);
}

이번 문제에서는 주어지는 수들의 범위가 1000000이하였기에 long long 타입을 써줘야 했다.

그리고 LCM(최소공배수)은 두 수의 곱을 최대공약수로 나눠주면 되기에 이렇게 하면 끝.