N개의 최소공배수

[문제]

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

 

[제한 사항]

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

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

 

[풀이]

def solution(arr):
    answer = 1
    for i in arr:
        answer = lcm(answer, i)
    return answer

# 최대공약수
def gcd(x, y):
    while y:
        x, y = y, x%y
    return x

# 최소공배수
def lcm(x, y):
    return x*y // gcd(x, y)

핵심은 유클리드 호제법을 반복적으로 수행해야한다는 것이다.

n개의 수의 최소공배수는 결국 n번째 수와 n-1번째 수까지의 최소공배수의 최소공배수라는 점에서, 최소공배수를 반복적으로 구한다고 생각하면 된다.