<프로그래머스 C++> n개의 최소공배수 (유클리스 호제법)

문제

n개의 수들의 배수 중 공통이 되는 가장 작은 최소공배수를 구하는 문제이다.

---

풀이 아이디어

두 수의 최소공배수는 아래 공식으로 구할 수 있다.

LCM(a, b) = a * b / GCD(a, b)

 

GCD는 최대공약수, LCM은 최소공배수이다.

이 공식을 이용해서 구해볼 것이다.

---

GCD와 LCM

GCD(최대공약수)

두 수를 모두 나눌 수 있어야 하므로 공통 인수 중에서 작은 것을 택한다.

12 = 2² × 3
 8 = 2³

공통 인수: 2
2²로 나누면 → 12/4=3, 8/4=2 (true)
2³으로 나누면 → 12/8=1.5 (false)

GCD = 2² = 4

 

LCM(최소공배수)

두 수를 모두 담을 수 있어야 하므로 공통 인수 중에서 큰 것을 택한다.

12 = 2² × 3
 8 = 2³

2³ × 3 = 24
24 / 12 = 2 (true)
24 / 8  = 3 (true)

LCM = 2³ × 3 = 24

---

문제 풀이

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int Gcd(int a, int b) {
    while(b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int Lcm(int a, int b)
{
    return a / Gcd(a, b) * b;
}

int solution(vector<int> arr) {
    int answer = arr[0];

    for(int i = 1; i < arr.size(); ++i)
        answer = Lcm(answer, arr[i]);

    return answer;
}

---

코드 흐름

1. GCD - 유클리드 호제법

int Gcd(int a, int b) {
    while(b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

GCD(a, b) = GCD(b, a%b) 원리를 반복문으로 구현했다.

b가 0이 되는 순간의 a가 최대공약수이다.

 

예시로 a = 12, b = 8일 때의 코드의 흐름을 표현하면 다음과 같다.

a=12, b=8  →  temp=8, b=12%8=4, a=8
a=8,  b=4  →  temp=4, b=8%4=0,  a=4
a=4,  b=0  →  종료
return 4

 

2. LCM()

int Lcm(int a, int b)
{
    return a / Gcd(a, b) * b;
}

a * b / GCD 의 공식을 사용한다.

a * b를 먼저 계산하면 Overflow가 발생할 수 있으므로 먼저 나누고 곱하는 순서로 작성했다.

 

3. n개의 LCM 계산

int answer = arr[0];
for(int i = 1; i < arr.size(); ++i)
    answer = Lcm(answer, arr[i]);

첫 번째 원소를 초기값으로 설정하고, 두 수씩 순서대로 LCM을 적용한다.

---

핵심 포인트

 

• GCD는 유클리드 호제법 GCD(a, b) = GCD(b, a % b)으로 구한다.
• LCM 공식은 a * b / GCD(a, b)이며, overflow 방지를 위해 a / GCD * b 순서로 계산한다.
• n개의 LCM은 두 수씩 순서대로 LCM을 적용한다.