N개의 최소공배수

첫번째 코드

 

최대 공약수를 구해서 모든 수에 나눈 후 최소 공배수를 구하면 되지 않을까?

 

def MOD(a, b):
    x = min(a, b)
    y = max(a, b)
    
    if x == 0:
        return y
    else:
        return MOD(x, y%x)

def solution(arr):
    answer = 1
    arr.sort()
    gcd = arr[0]
    
    for i in arr[1:]:
        gcd = MOD(gcd, i)
    
    for j in arr:
        answer *= (j/gcd)
    
    return int(answer*gcd)

 

오답...!

---

두번째 코드

 

제곱수와 같은 문제가 발생하는 것 같다.

최소공배수를 생각하면서 문제를 풀어야 할 것이다.

 

def GCD(a, b):
    x = min(a, b)
    y = max(a, b)
    
    if x == 0:
        return y
    else:
        return GCD(x, y%x)
    
def LCM(a, b):
    return a * b // GCD(a, b)

def solution(arr):
    arr.sort()
    lcm = arr[0]
    
    for i in arr[1:]:
        lcm = LCM(lcm, i)

    return lcm

 

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/12953.%E2%80%85N%EA%B0%9C%EC%9D%98%E2%80%85%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

programmers/프로그래머스/2/12953. N개의 최소공배수 at main · ornni/programmers