[Python] 프로그래머스 12940. 최대공약수와 최소공배수 (Lv.1)

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

 

최대 공약수와 최소 공배수를 구하는 문제입니다.

GCD를 이용해서 최대 공약수는 쉽고 빠르게 구할 수 있습니다.

 

최대 공약수를 구했다면, 최소 공배수는 N * M을 최대 공약수로 나눈 값입니다.

 

예를 들어 N과 M이 24, 36이라면

 

GCD(24, 36)

GCD(36, 24)

GCD(24, 12)

GCD(12, 0) -> 최대 공약수가 12

 

N * M = 864이고 864를 12로 나누면 최소 공배수인 72가 됩니다.

 

def solution(n, m):
    md = gcd(n, m)

    answer = [md, n * m / md]
    return answer


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)