[C++] 백준 1934번 : 최소공배수 (S5)

#문제

www.acmicpc.net/problem/1934

1934번: 최소공배수

#풀이 & 학습한 내용

유클리드 호제법으로 최대공약수(GCD)를 구하고 이를 통해 (a*b)/GCD로 최소공배수를 구해야하는 문제이다. supremo7.tistory.com/113에서 푼 방식으로 최소공배수(LCM)을 구하면 worst case에서 실행횟수가 약 1000*45000*45000로 약 2,000,000,000,000이다. 1억(1초)이 100,000,000이므로 불가능하다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main(void) {
    int a, b;
    int GCD;//최대공약수: greatest common divisor
    int LCM;//최소공배수: largest common multiple
 
    int T;
    cin >> T;
 
    while (T--) {
        cin >> a >> b;
        if (a < b) swap(a, b);//a>=b로 만들기
 
        int ta=a;
        int tb=b;
        int r=1;
        while (r != 0) {
            r = ta % tb;
            ta = tb;
            tb = r;
        }
        GCD = ta;
 
        LCM = (a*b) / GCD;
 
        cout << LCM << '\n';
    }
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Math/BOJ_1934.cpp

HoYoungChun/BOJ_algorithm