N개의 최소공배수

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

 

제한 사항

arr은 길이 1이상, 15이하인 배열입니다.

arr의 원소는 100 이하인 자연수입니다.

입출력 예

arr	result
[2,6,8,14]	168
[1,2,3]	6

---

문제 해설

 

최소공배수의 성질을 응용하자.

 

최소값의 최소공배수를 구해봐도 최댓값이 성립하지 않으면 최소공배수가 성립할 수 없다는 점을 기억하자.

 

예시에서 2와 6이 최소공배수를 만족해도,8이 만족할 수 없고, 2 6 8 이 만족해도 14가 만족할 수 없는것 처럼.

---

첫 번째 시도

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> arr) {
    int answer = 0;
    int maxA = *max_element(arr.begin(), arr.end());

    int i = 1;
    while (true)
    {
        answer = maxA * i;
        bool find = true;
        for (auto& def : arr)
        {
            if (find)
            {
                if (answer % def != 0) find = false;
            }
            else
                break;
        }
        if (find) return answer;
        i++;
    }
}

성공

 

최소공배수의 성질을 생각해서, 최댓값부터 N배수만큼 계속해서 만들고, 가지고있는 배열에 대해 해당 값을 계속해서 for문으로 0이 나타나는지 검사하면 된다.

만약, 한번이라도 false가 나타났다면 실패했다는 의미 임으로 다음 최소공배수를 시도한다.