[백준 1934] 최소 공배수

🔗문제 풀러가기
단계별로 풀어보기 단계 15의 1번째 문제이다.

문제 분석

유클리드 호제법을 이용하여 문제를 해결하였다.

코드

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

vector<int> lcms;

void Lcm(int a, int b)
{
    int tempA = a, tempB = b;
    while (tempB != 0)
    {
        int c = tempA % tempB;
        tempA = tempB;
        tempB = c;
    }
    lcms.push_back(a * b / tempA);
}

int main()
{
    int t;
    cin >> t;

    for (int i = 0; i < t; i++)
    {
        int a, b;
        cin >> a >> b;
        Lcm(a, b);
    }

    for (int i = 0; i < lcms.size(); i++)
    {
        cout << lcms[i] << endl;
    }
}

해석

1. 수를 입력받아 Lcm 함수를 실행해 최소 공배수를 구해 vector에 저장한다.

   Lcm 함수는 수를 입력받아 유클리드 호재법을 이용해
   최대 공약수를 구하여
   최소 공배수 = (두 수의 곱 / 최대 공약수)
   를 이용해 최소 공배수를 찾는 함수이다.

2. 이렇게 얻은 vector를 차례대로 출력하면 끝!