[프로그래머스] N개의 최소공배수

출처:: programmers.co.kr/learn/courses/30/lessons/12953#

분류::

 

1. 문제 이해 및 해결과정

 

2. 풀이방법

 1. 2개씩 빼서 최소공배수 구함

def lcd(a,b): #최소공배수 구하는 함수 
    x,y=a,b
    while a!=0:
        a,b=b%a,a #나머지, 나누는수
    return x*y//b
    
def solution(arr):
    
    while len(arr)>=2: #두개를 빼서 최대공배수 추가 
        a=arr.pop() 
        b=arr.pop()
        arr.append(lcd(a,b))
    
    return arr.pop()

 

3. 오답원인

 1. a,b,c의 최소공배수를 한꺼번에 구하면 틀림 ex) 2,3,4 

-> 2,3의 최소공배수를 구하고 구한 6과 4의 최소공배수를 구하는 방식으로 두개씩 차근차근 구해가야함

def solution(arr):
    arr.sort()
    minv=min(arr)
    res=1e9
    for i in range(1,minv+1):
        tmp=1
        flag=True
        for x in arr:
            if x%i!=0:
                flag=False
                break
            else:
                tmp*=x//i
        if flag==True:
            res=min(res,tmp*i)
    
    return res

 

4. 알게된 점