1934 최소공배수

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

T= int(read())
for _ in range(T):
    a,b = map(int,read().split())
    aa, bb = a, b

    while a % b != 0:
        a, b = b, a % b

    print(aa * bb // b)
    '

3. 풀이 및 생각

문제 풀이

최대 공약수를 “유클리드 호제법”을 통해 구할 수 있다. 최소 공배수란, 두 수를 곱한 후 일정 약수들을 나눠주면 되는데, 이 때, 일정 약수들이란 바로 최대 공약수이다.

예를 들면, 6과 10의 최대 공약수는 2이다. 그리고 최소 공배수는 다음과 같이 구할 수 있다. 6과 10을 약수로 표현한 후 곱하면 2x3x2x5 이다. 여기서 최대 공약수를 나눠주게 되면 2x3x5를 얻게 되고 이는 최소 공배수가 된다. 최대 공약수를 나눠주는 이유는 최대 공약수가 두 수의 공통된 모든 약수들의 곱으로 표현되기 때문에 중복을 없애주기 때문이다.

나의 생각

유클리드 호제법이란 것에 대해 처음 알게 되었다. 꼭 복습하자.