[백준] 1934번 최소공배수

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

 

문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

 

 

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

 

최대공약수(Greatest Common Divison) = 여러 수의 공통 약수 중 가장 큰 수

최소공배수(Least Common Multiple) = 여러 수의 공통 배수 중 가장 작은 수

 

ex) 6과 8의 최대공약수(GCD)는 2이고 최소공배수(LCM)은 24이다.

최대 공약수는 6X8 / GCD와 같다.

 

 

최초 코드

T = int(input())

for i in range(T) :
    number = []
    a, b = map(int, input().split())     

    if a or b == 1:
        result = (a * b)
    
    if a and b != 1 :
        for j in range(1, ((a*b)+1)) :
            if (a%j == 0) and (b%j == 0) :
                number.append(j)
                result = (a * b) / max(number)
    
    print(int(result))

딱 보기에도 효율적이진 못하다. 물론 케이스대로 출력은 됐으나 제출 시 시간 오류가 났다.

고민하다 방법을 못떠올려 검색해보니 유클리드 호제법이란게 있었고 해당 알고리즘으로 굉장히 간단하게 구현할 수 있었다.

 

유클리드 호제법

두 양의 정수 a, b (a > b)에 대하여 a, b의 최대공약수는 b,r의 최대공약수와 같다. 즉 gcd(a,b) = gcd(b,r)
r = 0이라면 a, b의 최대공약수는 b가 된다.

 

내용만 보면 무슨 말인지 이해가 잘 안간다. 3과 12로 예를 들어보자

3 % 12 = 3(r) (나머지가 r이 된다. r=3)

12 % 3 = 0(r) (나머지가 r이 돼서 r=0)

r = 0이 됐을 때 y 값인 3이 최대 공약수가 된다.

 

이걸 파이썬으로 구현하면 아래와 같다.

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

최소공배수는 a, b를 곱한 값에서 return 값인 최대공약수로 나누어주면 된다. 

 

 

정답

T = int(input())

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

for i in range(T) :
    a, b = map(int, input().split())
    gcd = (Euclidean(a, b))
    result = (a*b) / gcd
    print(int(result))

 

 

추가로 파이썬에는 math라는 라이브러리가 있다.

 

gcd()와 lcm()를 사용할 수 있어 쉽게 최대공약수와 최소공배수를 구할 수 있다.

* math.gcd()는 파이썬 3.9 버전부터 2개 이상의 인자도 받을 수 있다. (이하는 2개만 가능하다.)

* math.lcm()은 파이썬 3.9 버전 이후부터 사용 가능하다.

import math

# a=5 , b=10
a, b = map(int, input().split())
print(math.gcd(a, b)) ## 출력 값 5