[Python] 백준 2609 최대공약수와 최소공배수

브론즈 1 문제

(정답만이 아닌 개인적인 풀이 과정을 기록합니다)

 

---

 

코드를 설명하기 앞서 최대공약수와 최소공배수를

수학적으로 이해해보도록 하겠습니다.

 

왜 한 문제에서 두 개나 풀어야 돼? 할 수 있으나

최대공약수와 최소공배수는 짝꿍처럼 다닐 수 있는 친구입니다.

 

유클리드 호제법이라는 뭔가 대단해 보이는 방법으로 풀 수도 있지만

저는 개념을 찾아보고 적용하는 방식으로 접근했습니다.

 

거두절미하고

 

제가 참고한 개념을 보시겠습니다.

해당 개념을 통해

 

두 개의 입력값(a, b)에 대해 나누어 떨어지는 값 중 가장 큰 값(최대공약수, gcd)과

a/최대공약수 * b/최대공약수 * 최대공약수 (최소공배수, a*b/gcd)

 

도출할 수 있었습니다.

 

a, b = list(map(int, input().split()))
numa = []
numb = []

for i in range(2, min(a, b)):
    if a % i == 0:
        numa.append(i)
    if b % i == 0:
        numb.append(i)

numa.reverse()
numb.reverse()

for i in numa:
    for j in numb:
        if i == j:
            print(i)
            print(int(i*(a / i)*(b / i)))
            exit()

 

---

위에 코드는 실패한 코드입니다.

다음 두 가지 주제로 다시 한번

코드를 함께 살펴보도록 하겠습니다.

 

- 틀린 이유/ 반례 찾기

-  python 내장 함수( gcd, lcm)

- 최종 코드

 

 

 

1.  틀린 이유/ 반례 찾기

• 최대공약수를 찾는 범위

첫 번째 for문을 통해 a, b 중 작은 값까지 범위를 지정하였는데요. 이렇게 하면 둘 중 큰 값까지는 가지 않기 때문에

범위를 min(a, b)가 아닌 min(a, b)+1까지 해주어야 합니다.

 

또한 소수와 착각하여 범위의 시작이 2로 설정되어 있는데, 1이 되어야 합니다

 

예를 들어 3 3 입력일 때, 3까지 가지 못 하여 최대공약수가 1 값이 나오게 됩니다

 

 

 

 

2.  python 내장 함수( gcd, lcm)

• 최대공약수(gcd), 최소공배수(lcm)

import math

a, b = int(input)

print(math.gcd(a, b))
print(math.lcm(a, b))

 참고로 lcm함수는 python 3.9 이후부터 사용 가능하다고 합니다!

 

 

3.  최종 코드

a, b = list(map(int, input().split()))
numa = []
numb = []

for i in range(1, min(a, b)+1):
    if a % i == 0:
        numa.append(i)
    if b % i == 0:
        numb.append(i)

numa.reverse()
numb.reverse()

for i in numa:
    for j in numb:
        if i == j:
            print(i)                        #최대공약수
            print(int(i*(a / i)*(b / i)))   #최소공배수 #(a*b)/i
            exit()