[BOJ] 2609 - 최대공약수와 최소공배수 (🥈 실버 5티어, 🌟 유클리드 호제법)

사용 언어: Python3

문제

최대공약수와 최소공배수

유클리드 호제법 🌟

이 글을 참고했다.

2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단 a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r0를 구하고, 다시 r을 r0로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

즉, 아래와 같은 수식으로 나타낼 수 있다.

• 최대공배수 (GCD, Greatest Common Divisor)
  • 유클리드 호제법을 이용해 구할 수 있다.
• 최소공배수 (LCM, Least Common Multiple)
  • LCM = 두 자연수의 곱 // GCD

풀이

내 풀이

# ✅ 유클리드 호제법
def GCD(a, b):
    if b == 0:
        return a
    else:
        return GCD(b, a % b)

A, B = map(int, input().split())

gcd = GCD(A, B)
lcm = A * B // gcd # ✅ 최소공배수(LCM) -> 두 수의 곱 // GCD

print(gcd)
print(lcm)

• 테스트 케이스: 통과
• 제출 결과
  

다른 풀이

# ✅ 유클리드 호제법
def GCD(a, b):
    while b != 0:
        r = a % b
        a, b = b, r
    return a

A, B = map(int, input().split())

gcd = GCD(A, B)
lcm = A * B // gcd

print(gcd)
print(lcm)

• 재귀보다 이 방식이 좋은 것 같다!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기