[백준] 1934번 : 최소공배수

문제

 

---

풀이

 

주어진 두 수의 최소공배수를 구하는 문제이다. 설마 이 글을 보는 사람 중에 최소공배수를 모르는 사람이 있을 것이라고 생각하진 않는다. 혹시 두 수 A, B와 그들의 최소공배수 X, 최대공약수 Y가 있을 때 이들의 관계를 기억할지 모르겠다만...

A*B = X*Y 이다. 초등학교인가 중학교인가에서 배우는 것이니 왜 이렇게 되는 거냐고 묻지 않았으면 좋겠다.

 

아무튼 내가 하고 싶은 말은 최소공배수를 구하는 문제는 그냥 최대공약수를 구하는 문제와 같다는 것이다.

그럼 최대공약수를 구하는 알고리즘은 어떻게 짜면 좋을까?

 

A<=B라고 할 때

1. for(int i=A ; i>=1 ; i--)의 for문을 돌며 처음으로 A%i == 0 && B%i == 0가 되는 i 찾기

2. for(int i=A ; i>=1 ; i/=2)의 for문을 돌며 처음으로 A%i == 0 && B%i == 0가 되는 i 찾기

3. 1, 2번 방법과 비슷한 기타 등등...

4. 유클리드 호제법

 

1, 2번 방법은 간단하고 떠올리기도 쉽지만 시간초과될 위험성이 있다. 그럼 유클리드 호제법은 무엇인가?

ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

이산수학때 배운 것 같은데 잘 기억은 안나고 대충 공식만 빼먹자면

 

이렇게 되겠다. 이 내용을 코드로 작성하면 된다.

---

소스코드

 

#include <iostream>

using namespace std;

int gcd(int a, int b) { //유클리드 호제법으로 최대공약수 구함
    int temp, n;

    if (a < b) {
        temp = a;
        a = b;
        b = temp;
    }
    while (b != 0) {
        n = a % b;
        a = b;
        b = n;
    }
    return a;
}

int main() {
    int T, A, B;

    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> A >> B;
        cout << (A * B) / gcd(A, B) << '\n'; //함수로 구한건 최대공약수니까 최소공배수로 변환
    }
}

우리가 구하려 하는 것이 최소공배수였다는 것을 잊지말자.