[2609] 최대공약수와 최소공배수/ 파이썬 (배웠던거 써먹기)

 

문제 링크: https://www.acmicpc.net/problem/2609

 

2609번: 최대공약수와 최소공배수

 

최대공약수 ㅋㅋㅋ 배웠던 거가 나왔다. 유클리드 호제법을 이용하기!

샛길공부로 따로 자세하게 써놓은 글은 여기로 아래로👇👇👇👇

2021.11.22 - [코딩공부/파이썬 공부] - [샛길공부] 파이썬 최대공약수와 최대공배수 구하는 여러가지 방법

다... 그래서 틀린걸까

---

❌ 1차시도 실패

최소공배수에서 return을 할 때, a,b가 재귀함수 돌면서 바뀔거라는 걸 생각안함...

그래서 실패.. !! 그래서 방법은! 아래에 나와있다!

---

❓ 정답은 ??

a,b = map(int,input().split())
 
 
#최대공약수(유클리드호제법)
def result_1(a,b):
    if a%b==0:
        return b
    else:
        return result_1(b, a%b)
 
c,d=a,b
#최대공배수(최대공약수로 나눈 몫들과 최대공약수를 곱한 값)    
def result_2(a,b):
    if a%b==0:
        return int(b*(c/b)*(d/b))
    else:
        return result_2(b, a%b)
    
print(result_1(a,b))
print(result_2(a,b))

✨다른 분들의 최대공배수 풀이를 보니!

그냥 주어지는 두 값을 곱하고 최대공약수를 나누는 방법을 쓰고 있었다!

역시 다른 분들의 방법을 보는 것 또한 배움을 키우는 것!

---

💯 풀이 과정

1)최대공약수는 유클리드호제법으로 쉽게 도출!

#  유클리드 호제법 : 두 자연수 A,B(A>B)에서 A%B==R이면, 

#  A와B의 최대공약수는 B와R의 최대공약수와 동일

2)최대공배수는

 2-1) 일단 보니까 주어진 각 값을 최대공약수로 나눈 다음

 2-2) 나온 각 몫들의 곱과 최대공약수들의 곱으로 답 도출!

 (주의할 점! 재귀 함수를 돌면서 처음 a,b값이 바뀌어버릴 수 있으니 미리 c,d로 복제해놓고 답 도출 시 사용하기!)

 

🎀가장 쉬운 방법은! 파이썬 내장함수 이용하기!

import sys
math.gcd(a,b)  #최대공약수
math.lcm(a,b)  #최소공배수

---

😎오늘의 한줄평: 배운거 써먹기!