[백준][C++] 1934 : 최소공배수

 

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

 

 

 

 

---

- 문제

 

  두 수가 주어지면 두 수의 최소 공배수를 구하는 문제다.

 

 

---

- 해설

 

  유클리드 호제법이라는 것을 알게 되었는데, 이것을 이용하면 최소공배수, 최대공약수 문제가 쉽게 풀린다.

 

 

 

---

- 풀이

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

int gcd(int x, int y)
{
    return (x % y == 0) ? y : gcd(y, x % y);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T, A, B;
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        cin >> A >> B;
        if (A >= B)
            cout << A * B / gcd(A, B) << '\n';
        else
            cout << A * B / gcd(B, A) << '\n';
    }
    return 0;
}

 

---

- 새롭게 알게 된 점

 

유클리드 호제법

int gcd(int x, int y)
{
    return (x % y == 0) ? y : gcd(y, x % y);
}

1. x와 y로 나눈다

  - 나눠지면 y가 최소공배수

  - 아니면 y의 최소공배수를 구하러 감

 

2. y와 x%y를 나눈다.

  - 나눠지면 x%y가 최소공배수

  - 아니면 반복