N개의 최소공배수

 

- 관련 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

 

N개의 수가 주어졌을 때, 최소공배수를 구하는 문제이다.
"1934번: 최소공배수" 문제에서 확장된 문제로 볼 수 있다.

두 숫자의 최소공배수를 구하고 구해진 최소공배수와 다음 수의 최소공배수 값을 구하는 방식으로 풀었다.

 

1) A 와 B 중 작은 수 확인

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

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

4) 1)에서 3)까지의 과정을 통해 최소공배수와 C 두 수의 최소공배수 구하기

 

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

int getLCM(const 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 solution(vector<int> arr) {    
    int answer = arr[0];
    
    for (int i = 1; i < arr.size(); i++)
        answer = getLCM(answer, arr[i]);
    
    return answer;
}

 

최대공약수를 구하는 함수를 재귀함수로 구현하여 풀어줄 수도 있다.

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

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

int getLCM(const int A, int B)
{
    return (A * B) / getGCD(A, B);
}

int solution(vector<int> arr) {    
    int answer = arr[0];
    
    for (int i = 1; i < arr.size(); i++)
        answer = getLCM(answer, arr[i]);
    
    return answer;
}

 

* 연관 문제:

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