백준) 1934번 최소공배수 문제 (파이썬)

문제) 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다.

 

이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다.

 

예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

 

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

T = int(input())   # 유클리드 호제법
for i in range(T):  
    a, b = map(int,input().split())
    x, y = a, b
    while y != 0:   # y가 0이 아니면 계속 반복
        temp = x  # temp = 6, 10, 6, 4
        x = y     # x = 10, 6, 4, 2
        y = temp % y  # y = 6, 4, 2, 0
    print(a * b // x)    # 최소공배수 = 두 자연수의 곱 / 최대공약수

이번 문제는 유클리드 호제법을 이용하여 문제를 풀었다.

 

유클리드 호제법은 최대공약수를 구하는 알고리즘이다.

 

소인수분해를 통해 최대공약수를 구한다.

 

다음 a 와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다는 성질을 이용한다.

 

그래서 위와 같은 코딩이 나오게 되었다. 

 

처음에는 이해가 되지 않아 직접 숫자를 넣어보면서 이해하였다.

 

한번 이해가 되니 공식도 이해가 되었다.

 

천천히 다시 볼 필요가 있는 문제인 것 같다.

 

이해가 안되시거나 틀린 정보는 댓글로 알려주시면 감사하겠습니다!