1934번 : 최소공배수

[ 문제 ]

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

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

[ Input ]

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

[ Output ]

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

---

[ 풀이1 ]

단순하게 풀어보고 싶어서 쓴 코드이다. 이렇게 하면 시간초과 나오더라... 슬펐다ㅠ

그래도 왜 이렇게 풀었는지 설명해보자면..!

 

최소공배수는 두 숫자의 공배수 중 가장 작은 수 이므로 두 수 보다 크거나 같은 숫자이다. 또한 공약수가 없다면 최소공배수는 두 수의 곱과 동일하므로 두 숫자의 최댓값부터 두 수의 곱까지 반복문을 만들었다.

두 숫자 중 최댓값부터 두 숫자로 각각 나눴을 때 동시에 나누어 떨어진 수가 공배수일 것이고 가장 처음 나누어 떨어졌을 때가 최소이므로 break 해서 반복문을 종료한다.

[ 코드1 ]

# 테스트 케이스의 개수 T
T = int(input())

# 최소공배수 구하기
for _ in range(T):
    A, B = map(int, input().split())
    
    for i in range(max(A, B), A*B+1):
        if (i % A == 0) and (i % B == 0):
            print(i)
            break

[ 풀이2 ]

제일 정석적인 풀이로 풀어봤다. 가장 대표적인 공식인 LCM=(A*B)/GCD 을 사용한다.

LCM은 Least Common Multiple 로 최소 공배수를 의미하고, GCD는 Greatest Common Divisor로 최대 공약수를 의미한다. GCD 또한 위의 코드처럼 하나씩 줄여가며 찾을 수도 있지만 또 시간초과 될 수도 있으므로 이번엔 유클리드 호제법을 사용할 것이다.

 

유클리드 호제법을 이용한 풀이는 이 영상에서 설명하고 https://www.youtube.com/watch?v=R1gxRwXRpMQ 그에 대한 증명은 https://www.youtube.com/watch?v=J5Yl2kHPAY4 이 영상을 참고 했다. 나중엔 직접 풀이법 및 증명방법까지 정리해봐야징!!

[ 코드2 ]

# 최대공약수 구하는 함수
def get_gcd(a, b):
    a, b = (max(a, b), min(a, b))
    
    while a % b != 0:
        a, b = (b, a % b)
        
    return b
    
    
# 테스트 케이스의 개수 T
T = int(input())

# 최소공배수 구하기
for _ in range(T):
    A, B = map(int, input().split())
    
    GCD = get_gcd(A, B)
    LCD = int(A*B / GCD)
    
    print(LCD)