[준비운동 PART1. 튼튼한 기본기] 최대공약수와 최소공배수(2609번)

1. 문제 설명

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

2. 나의 풀이

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

# 유클리드 호제법, 최대공약수 구하기
def GCD(x, y):
    while(y):
        x,y = y, x%y
    return x

# 최소공배수 구하기
def LCM(x, y):
    result = (x*y)//GCD(x,y)
    return result

print(GCD(a, b))
print(LCM(a, b))

유클리드 호제법이란?

x, y의 최대공약수는 y, r의 최대공약수와 같다는 것을 이용한 방법이다. (x%y = r)

즉, 계속해서 x에 y를 대입하고 y에는 r(x%y)을 대입하다보면,

언젠가는 r(x%y)이 0일 때가 있다.

나머지의 값이 0일 때의 y값이 최대공약수이다.

최소공배수는 x*y를 최대공약수로 나눈 몫이다.

그냥 풀면 시간초과가 나고 유클리드 호제법을 사용해야 통과한다!