[프로그래머스💯] 코딩테스트 연습 > 연습문제 > N개의최소공배수

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

 

import functools
import sys

sys.setrecursionlimit(10 ** 6)


def solution(arr):
    def getGCD(a, b):
        if a==0:
            return b
        if a < b:
            a, b = b, a
        return getGCD(a%b, b)

    def getLCM(a, b):
        factor = getGCD(a, b)
        return int(a*b / factor)
    return functools.reduce(getLCM, arr)

풀이)

LCM : 최소공배수

r : 최대공약수

 

a = r * a' 

b = r * b'

LCM = r * a' * b' 

따라서 a, b 의 최소공배수 = a * b / r

( LCM = a*b/r)

 

 이를 이용해서 풀면 된다.

 

0) setreculsionlimit(10**6) => 재귀함수의 깊이 제한을 늘려주기

 

1) getGCD (최대공약수 구하기)

유명한 알고리즘이다 큰수에서 작은수를 계속 나누는 작업을 나머지가 0 이 될때까지 반복한다.

 

2) getGCD를 이용해 최소공배수를 구함.

 

3) 2개 요소씩 배열을 순차적으로  최소공배수를 구해주면 배열의 마지막에는 모든 수의 최소공배수가 되어 있다.

(reduce를 이용해 한번에 계산)

 

(* 다른 풀이를 보니 파이썬 내장함수에 gcd가 있는데 그걸 써도 된다.)

 

 

* 이 문제 및 로고의 저작권은 Programmers에 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges