1934번: 최소공배수

- 관련 사이트: https://www.acmicpc.net/problem/1934

1934번: 최소공배수

 

자연수 A와 B의 최소공배수를 구하는 문제이다.

최대공약수를 찾은 후 해당 값을 통해 최소공배수를 계산해주었다.

 

1) A 와 B 중 작은 수 확인

2) 작은 수부터 2까지 두 수로 모두 나누어지는 가장 큰 값 확인 = 최대공약수

3) (A * B) / 최대공약수 = 최소공배수

 

#include <iostream>
using namespace std;

int getLCM(int A, int B)
{
    int small = A < B ? A : B;
    int gcd = 1;
    for (int i = small; i > 1; i--)
    {
        if (A % i == 0 && B % i == 0)
        {
            gcd = i;
            break;
        }
    }
    
    return (A * B) / gcd;
}

int main()
{
    int T, A, B;
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        cin >> A >> B;
        cout << getLCM(A, B) << "\n";
    }
    return 0;
}

- 메모리: 2020 KB

- 시간: 172 ms

- 코드 길이: 425 B

 

아래와 같이 최대공약수 구하는 함수를 재귀 함수 형식 (유클리드 호제법) 으로도 문제를 풀어줄 수 있다.

 

#include <iostream>
using namespace std;

int getGCD(int A, int B)
{
    return B ? getGCD(B, A % B) : A;
}

int main()
{
    int T, A, B;
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        cin >> A >> B;
        cout << (A * B) / getGCD(A, B) << "\n";
    }
    return 0;
}

- 메모리: 2020 KB

- 시간: 40 ms

- 코드 길이: 283 B

 

 

* 연관 문제:

- [프로그래머스] N개의 최소공배수