문제
접근
두 수의 최대 공배수를 구하는 방법은 간단하다.
최대 공배수 = 두 수의 곱 / 최소 공약수
최소 공약수는 유클리드 호제법을 이용하면 된다.
그렇다면 여러 개의 숫자의 최대 공배수는 어떻게 구할까?
복잡하게 생각할 것 없이, 최대 공배수를 n-1번 구해주면 된다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(arr):
arr.sort()
answer = arr[0]
for i in range(1,len(arr)):
n = gcd(answer, arr[i])
answer = answer * arr[i] / n
return answer
def gcd(a,b):
while a != 0:
n = b % a
if n==0:
return a
b = a
a = n
return 1