[BOJ] Python 백준 2436번 공약수 골드 5

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

2436번: 공약수

문제 풀이

---

최대 공약수와 최소 공배수에 관한 수학 문제이다.

 

문제에 들어가기 앞서 최대 공약수와 최소 공배수에 대한 관계와 최대 공약수를 구하는 방법인 유클리드 호제법을 알고 있어야 수월하게 풀 수 있다.

 

간단하게만 설명하자면 두 수 A, B가 있을 때 동시에 나눠서 나머지가 0이 되는 가장 큰 수를 최대 공약수라 하고 A의 배수, B의 배수 중 가장 작은 수를 최소 공배수라 한다.

 

여기까지는 누구나 알고 있지만 관계에 대해서 이해해야 보다 수월하게 풀 수 있다.

 

최대 공약수를 c, 최소 공배수를 d라 하고 A를 c로 나눈 몫을 a, B를 c로 나눈 몫을 c로 한다면 a와 b는 서로소 관계(1을 제외한 공약수가 없는 관계)가 된다.

 

따라서 a x b x c = d 가 성립하기 때문에 이를 자유자재로 이용할 수 있어야 한다.

 

또한 유클리드 호제법은 두 수가 있을 때 큰 수를 작은 수로 나눈 나머지가 0이 될 때까지 반복하여 최대 공약수를 구하는 방식이다.

 

전체 코드에서 구현 방법을 보면 이해될 것이다.

 

def gcd(num1,num2):
    if num2%num1==0:
        return num1
    else:
        return gcd(num2%num1,num1)
a,b=map(int,input().split())
b=b//a
res=[]
for i in range(1,b+1):
    if b%i==0:
        if i<b//i:
            if gcd(i,b//i)==1:
                res.append([i*a+(b//i)*a,i*a,(b//i)*a])
        else:
            if gcd(b//i,i)==1:
                res.append([i*a+(b//i)*a,(b//i)*a,i*a])
if len(res)>0:
    res.sort(key=lambda x:x[0])
    print(res[0][1],res[0][2])

 

먼저 유클리드 호제법을 사용하는 최대 공약수를 구하는 함수를 gcd로 선언했다.

 

gcd는 최대 공약수(Greatest Common Divisor)의 약자이기 때문인데, 이처럼 코드를 작성할 때는 해당 변수가 무엇을 뜻하는지, 해당 함수가 어떤 기능을 하는지 의미하는 이름으로 짓는 게 차후에 코드를 이해하기 편해서 좋다.

 

num2가 num1보다 더 큰 수이고 함수를 보면 알 수 있듯이 큰 수를 작은 수로 나눴을 때 나머지가 0이면 작은 수를 리턴, 아니라면 나머지와 나눴던 작은 수를 매개변수로 재귀 호출한다.

 

이렇게 반복하면 최대 공약수를 얻을 수 있다.

 

7번째 줄에서 b를 a로 나눈 몫으로 저장하는 이유는 최소 공배수에서 최대 공약수를 없애고 서로소인 두 수의 곱만 고려하기 위해서다.

 

만약 서로소 관계인 두 수를 구한다면 각 각 최대 공약수를 곱해서 출력하면 답을 구할 수 있을 것이기 때문이다.

 

8번째 줄의 res 리스트는 서로소인 두 수와 두 수의 합을 저장하는 용도다.

 

문제에서 분명 조건에 부합하는 자연수 쌍은 여러 개 있을 수 있는데 두 자연수의 합이 최소인 경우를 출력하라 했으니 합을 기준으로 정렬하여 가장 작은 경우를 출력하면 될 것이다.

 

따라서 9번째 줄에서 1부터 b까지 반복을 하는데 i로 b를 나눈 나머지가 0이면 두 수의 곱으로 나타낼 수 있는 숫자고 두 번째 if문은 더 큰 수를 gcd 함수의 두 번째 인자에 넣기 위한 조건문이다.

 

또한 gcd 함수의 반환 결과가 1이라면 두 수가 서로소 관계이므로 두 수의 합과 두 수를 최대 공약수를 곱해서 res 리스트에 넣었다.

 

반복문이 종료되면 res 리스트를 두 수의 합을 기준으로 오름차순 정렬하고 첫 번째 원소에 들어가 있는 두 수를 출력하면 통과한다.

 

결과 화면

 

문제를 통과하긴 했지만 조금 더 생각하면 탐색하는 범위를 절반 정도로 줄일 수 있을 것 같다.