쉬운문제였다. 물론 한번 틀려서 유클리드 호제법 공부하고 왔다.
처음에는 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)
'알고리즘' 카테고리의 다른 글
백준 2981 풀이 (검문, 유클리드 호제법, 약수 구하기) (0) | 2021.03.01 |
---|---|
백준 1934 풀이 (최소공배수, 유클리드 호제법) (0) | 2021.02.28 |
백준 13305 풀이 (주유소, 그리디 알고리즘) (0) | 2021.02.28 |
백준 1541 풀이 (잃어버린 괄호, 그리디) (0) | 2021.02.26 |
백준 11399 풀이 (ATM, 그리디) (0) | 2021.02.26 |