Level 2 N개의 최소공배수 Python3

programmers.co.kr/learn/courses/30/lessons/12953

코딩테스트 연습 - N개의 최소공배수

 

최종 코드

• GitHub github.com/hwayeon351/Programmers-Algorithms

hwayeon351/Programmers-Algorithms

from math import gcd
def get_lcm(a, b):
    return a * b // gcd(a, b)

def solution(arr):
    lcm = arr[0]
    for i in arr[1:]:
        lcm = get_lcm(lcm, i)
    return lcm

 

---

풀이 과정

풀이 시간  7분

1. 두 수의 최소공배수 구하기

from math import gcd
def get_lcm(a, b):
    return a * b // gcd(a, b)

 두 수 a와 b가 있다면, a와 b의 공통된 배수 가운데 최솟값이 최소공배수이다.

따라서 최소공배수는 두 수의 곱을 두 수의 최대공약수로 나눈 것과 같다.

만약, a = 6, b = 18일 때, 최소공배수 = 6 * 18 / 6 = 18이다.

그래서 최소공배수를 구하기 위해서는 두 수의 최대공약수를 구해야한다.

최대공약수는 a의 약수이면서 b의 약수인 수 중 최댓값을 말한다.

파이썬은 math 모듈에서 최대공약수를 구하는 함수를 제공한다.

 

 

2. N개의 최소공배수 구하기

 그렇다면 N개의 최소공배수는 어떻게 구할까?

N개의 최소공배수는 먼저 두 수의 최소공배수를 구하고, 그 값과 다른 수의 최소공배수를 구해나가면 된다.

def solution(arr):
    lcm = arr[0]
    for i in arr[1:]:
        lcm = get_lcm(lcm, i)
    return lcm

 

 

---

참고

• 2021/01/14 - [Python/라이브러리] - math

math