프로그래머스 12953 Python / N개의 최소공배수

안녕하세요.

 

이번엔 프로그래머스 12953 N개의 최소공배수 문제를 파이썬으로 풀어보겠습니다.

문제 링크는 여기입니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12953?language=python3 

프로그래머스

 

---

풀이

 

여러 수의 최소공배수는 각자의 최소공배수를 계속 구해주면 됩니다.

예를 들어, 2, 6, 8, 14 라고 한다면

2와 6의 최소공배수를 구하고, ---- 6

그 최소공배수인 6과 8의 최소공배수를 구하고, ----- 24

그 최소공배수인 24와 14의 최소공배수를 구하면 됩니다. => 168

 

최소공배수는, 최대공약수(gcd)를 구한 뒤, 

두 수를 곱하고 최대공약수로 나누면 그것이 최소공배수가 됩니다.

2와 6으로 하면, 최대공약수는 2 이므로, 최소공배수는 2*6/2 = 6이 됩니다.

 

코드로 보면 다음과 같습니다.

def gcd(a, b):  # 최대공약수
    for i in range(min(a, b), 0, -1):
        if a % i == 0 and b % i == 0:
            return i
    return -1

def solution(arr):
    answer = 1
    for i in arr:
        answer = answer * i // gcd(answer, i) # 최소공배수 구하기
        
    return answer

 

감사합니다.