[백준/Python] 13241번 최소공배수

[백준/Python] 13241번 최소공배수

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

def lcm(a, b):
    return a * b // gcd(a, b)

a, b = map(int, input().split())
print(lcm(a,b))

문제에서 설명하는 것은 지난 최소공배수에서 사용한 '유클리드 호제법'에 대해서 설명하고 있다.

유클리드 호제법

• 두 자연수의 최대 공약수(Greatest Common Divisor, GCD)를 효율적으로 찾는 알고리즘이다.

1. 나머지 연산을 사용한 반복 : 두 수 a와 b에 대해서(a > b인 경우), a를 나눈 나머지를 구한다. 나머지를 r이라고 하고, a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다
2. 반복 과정 : 이제 b와 r에 대해 같은 과정을 반복한다. 즉, b를 r로 나눈 나머지를 구하고, 이를 새로운 r로 사용한다. 나머지가 0이 될 때 까지 반복한다.
3. 최대 공약수 결정 : 나머지가 0이 되면, 나누는 수가 a와 b의 최대 공약수가 된다. 이는 나머지가 0이 되었다는 것은 바로 전 단계의 나누는 수가 나누어지는 수의 약수라는 것을 의미하고 이는 두 수의 공통된 약수 중 가장 큰 값이 된다.

예시)
1. 48 과 18 이 있다고 하자. 48 을 18로 나누면 나머지는 12이다
2. 이제 18을 12로 나누면 나머지는 6이다.
3. 12를 6으로 나누면 나머지는 0이다.
4. 나머지가 0 이므로 최대 공약수는 6이 된다.