최소공배수(LCM) 한 방에 끝내기: lcm = a*b // gcd(a,b) + 누적

최소공배수(LCM) 한 방에 끝내기: lcm = a*b // gcd(a,b) + 누적

 

프로그래머스에서 자주 나오는 문제 중 하나가 “배열에 있는 숫자들의 최소공배수(LCM)를 구하라” 입니다.
피보나치처럼 커질 수 있는 값도 아니고, 수학 공식 하나만 이해하면 코드가 엄청 단순해져요.

핵심 아이디어 1) GCD(최대공약수)와 LCM(최소공배수)의 관계

두 정수 a, b에 대해 다음이 항상 성립합니다.

• lcm(a, b) = a * b // gcd(a, b)

왜냐면, g = gcd(a,b)라고 할 때
a = g * a', b = g * b'로 쓸 수 있고(공통인수 g를 뽑아낸 형태),
이때 a'와 b'는 서로소라서(겹치는 인수가 없음) 두 수를 모두 포함하는 최소 배수는

• lcm(a,b) = g * a' * b'

가 됩니다.
또한 a*b = (g*a')*(g*b') = g^2 * a' * b' = g * (g*a'*b') = g * lcm(a,b) 이므로
결국 lcm(a,b) = a*b / g가 됩니다.

그리고 LCM은 정수이기 때문에 나눗셈은 /가 아니라 정수 나눗셈 // 로 처리합니다.

---

핵심 아이디어 2) 배열 전체 LCM은 “앞에서부터 누적”

배열 arr = [a, b, c, ...]의 최소공배수는

• lcm(a, b, c, ...) = lcm(lcm(a, b), c, ...)

처럼 순서와 상관없이 누적해서 구할 수 있습니다.

즉,

1. 첫 번째 값으로 시작하고
2. 다음 값을 하나씩 합치면서 lcm으로 갱신하면 끝!

---

정답 코드 (파이썬)

 

from math import gcd

 

def solution(arr):

 

l = arr[0] for x in arr[1:]:

l = l * x // gcd(l, x)

 

return l