[C++] Programmers | N개의 최소공배수

N개의 최소공배수

프로그래머스

---

✍🏻 풀이

이 문제는 벡터의 원소들을 순회하며 차곡차곡 최소공배수를 구해 나가면 되는 아주 간단한 문제였다.

두 수 A, B의 최소공배수는 A * B / (A, B의 최대공약수) 라는 관계가 성립하기 때문에

우선 A, B의 최대공약수를 구한 후, 식에 대입하여 최소공배수를 구하였다.

 

💡 유클리드 호제법

나는 최대공약수를  대표적인 알고리즘인 유클리드 호제법을 사용하였다.

 

호제법이란, 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이다.

a를 b로 나누어 나머지인 b'을 구하고,

b를 b'으로 나누어 나머지인 b''을 구하고,

...

이렇게 서로를 나누어 구해진 나머지가 0이 될 때까지 반복하면 두 수의 최대공약수를 구할 수 있다.

이를 재귀적으로 구현하면 아래 코드로 나타낼 수 있다.

long long GCD(int a, int b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}

---

✅ Accept Code

// programmers week6-2
// N개의 최소공배수

#include <bits/stdc++.h>

using namespace std;

long long GCD(int a, int b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}

long long LCM(int a, int b) {
    return a * b / GCD(a, b);
}

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

---

Reference

유클리드 호제법 - 나무위키

 

유클리드 호제법이란? | Lonpeach Tech