백준 2609 풀이 (최대공약수와 최소공배수, 유클리드 호제법)

쉬운문제였다. 물론 한번 틀려서 유클리드 호제법 공부하고 왔다.

처음에는 a와 b중에 작은 수에서 1씩 빼면서 둘다 나누어 떨어지는지 확인하는 방식을 통해 최대 공약수를 구하려고 했다. 물론 그 방법이 틀렸다고는 할 수 없지만, 문제는 시간도 오래걸리고 좋은 방법 같지 않았다.

그래서 찾아보니 유클리드 호제법이라는 엄청난 방법이 있었다.

 

(a,b)가 존재할때 a%b를 하여 나머지를 계속해서 나누어주는 방법이다.

(24, 18) => 24 % 18 = 6

(18, 6) => 18 % 6 = 0

(6, 0) => 최대 공약수는 6

 

이러한 방식으로 몇개의 연산으로 최대 공약수를 찾을 수 있는 것이다. 기존보다 연산의 횟수가 획기적으로 줄어들게 된다. 요 방식으로 최대 공약수를 찾으면 최소 공배수는 쉬워진다.

24 // 6 = 4

18 // 6 = 3

4*3*6 = 최소 공배수 72

(*만약 최대 공약수가 1이면 두 값을 곱하면 된다.)

 

즉, 최대 공약수만 찾으면 최소 공배수 찾는 것은 아주 식은죽 먹기라는 것이다.

tmp = list(map(int, input().split()))
if tmp[0] < tmp[1]:
    t = tmp[0]
    tmp[0] = tmp[1]
    tmp[1] = t
a = tmp[0]
b = tmp[1]
# get 공약수
yak = 0
while 1:
    c = tmp[0] % tmp[1]
    tmp[0] = tmp[1] 
    tmp[1] = c
    if tmp[1] == 0:
        break
yak = tmp[0]
if yak == 1:
    print(tmp[0])
    be = a*b
    print(be)
else:
    print(yak)
    a = a // yak
    b = b // yak
    print(yak * a * b)