[C++로 풀이] N개의 최소공배수 ⭐⭐

📌 N개의 최소공배수

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

3개 이상의 수에서 최소공배수를 구할 때, 공약수가 없다면 모든 수에서 서로소가 나올 때까지 일부의 공약수만으로 계속 나눈다!

처음엔 두 수의 최소 공배수를 구하는 것처럼 최대공약수 * 두 수의 서로소 이렇게 구하려고 했었는데 그렇게 하니 오답이 났었다. 3개 이상의 수에선 좀 다르구나..⭐ 4와 16이 3으로 나눠지지 않더라도 일단 3 과 9의 공약수인 3으로 나누고 그 이후엔 4 와 16의 공약수인 4로 나누고 나중에 3 x 4 x 3 x 4 = 144 이게 최소공배수가 된다.

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

using namespace std;

int solution(vector<int> arr) {
    int answer = 1;
    
    int max = *max_element(arr.begin(), arr.end());
    int cur = max;
    while(true)
    {
        bool flag = true;
        for(int i = 0; i < arr.size(); i++)
        {
            if (cur % arr[i] != 0)
            {
                flag = false;
                break;
            }
        }
        
        if (flag)
        {
            answer = cur;
            break;
        }
        else
            cur += max;
    }
    
    return answer;
}

최소공배수를 구하는거니까 arr의 원소들 중 가장 최대값의 배수들 중에 최소공배수가 있을 것임을 생각할 수 있다! 최대값의 배수에서 arr의 원소들이 전부 나누어 떨어지는 수를 처음으로찾으면 그게 바로 최소 공배수.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기