[백준/파이썬] 2609번: 최대공약수와 최소공배수 풀이

🔗 문제 링크

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

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

  최대공약수와 최소공배수를 구하는 문제이다. 나는 단순 구현으로 풀었는데 풀이를 찾아보니 유클리드 호제법을 사용하면 훨씬 간단하게 풀 수 있다! 머리가 무식하면 몸이 고생한다는 걸 체감했다... 

 

---

🔎 문제 풀이 & 작성 코드

  나는 최대공약수와 최소공배수의 정의에 입각해서 코드를 작성하였다. 두 수가 주어졌을 때 최대공약수는 두 수의 공통된 소인수들의 곱이고, 최소공배수는 두 수들의 공통된 배수중에 가장 작은 수이다. 최소공배수를 그래서 최대공약수는 greatest, 최소 공배수는 least라는 변수로 선언해 둔 다음, 소인수 분해의 과정을 동시에 진행하면서, 최대공약수는 공통된 소인수들만 곱해주고 최소공배수는 공통으로 갖는 소인수에, 포함되지 않은 두 수의 나머지 소인수들까지 곱해주어서 구하였다. 작성한 코드는 다음과 같다.

A, B = map(int, input().split())
least, greatest = 1, 1

n = 2

while A > 1 or B > 1:
    if A % n == 0 and B % n == 0:
        least *= n
        greatest *= n
        A = A//n
        B = B//n
    elif A % n == 0 and B % n != 0 :
        greatest *= n
        A = A//n
    elif A % n != 0 and B % n == 0:
        greatest *= n
        B = B//n
    else:
        n += 1

print(least)
print(greatest)

 

  하지만,, 이 코드를 정말 간단하게 작성할 수 있는 방법이 있었다!! 앞에서 말했듯이 유클리드 호제법을 사용하면 된다. 

 

  유클리드 호제법은, 두 수 A, B (A > B)가 있을때, A와 B의 최대공약수는 B와 R(=A%B ; A를 B로 나누었을 때의 나머지)의 최대공약수와 같다! 이러한 성질에 따라 B를 R로 나누었을 때의 나머지 R'(=B%R)을 구하고, 이를 계속 반복해 나가다가 나머지가 0이 되었을 때 나누는 수가 A와 B의 최대공약수라고 한다. 최소공배수는 A와 B의 곱을 A와 B의 최대공약수로 나누면 구할 수 있다. 이러한 원리에 따르게 되면 다음과 같이 코드를 작성할 수 있다.

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

def gcd(A, B):
    while B > 0:
        A, B = B, A % B
    return A

def lcm(A, B):
    return A * B // gcd(A, B)

print(gcd(A, B))
print(lcm(A, B))

 

  해당 내용을 작성하면서 다음 벨로그를 참조하였습니다!

백준 - 2609 (Python) - 최대공약수와 최소공배수

 

 

---

🌍 깃허브 링크

실제 작성한 해당 정답 코드는 깃허브에도 업로드해두었습니다.

dohyun-99 - Overview