[알고리즘] BOJ 2436 공약수

[BOJ] 2436 공약수 바로가기

📍 문제

어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다.

예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다.

이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다.

예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다. 그러나, 최대공약수가 6이며 최소공배수가 20인 두 자연수는 있을 수 없다.

두 개의 자연수가 주어졌을 때, 이 두 수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 구하는 프로그램을 작성하시오.

---

📍 입력

첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,000,000 이하이다.

---

📍 출력

첫째 줄에는 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 크기가 작은 수부터 하나의 공백을 사이에 두고 출력한다. 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수 쌍이 여러 개 있는 경우에는 두 자연수의 합이 최소가 되는 두 수를 출력한다.

---

📍 풀이

✍ 문제 풀이

• 최대 공약수와 최소 공배수의 값을 이용해 합이 최소가 되는 두 자연수를 반환하는 함수 check(gcm, lcm) 함수와 인자로 받은 두 자연수가 서로소인지 확인하는 eo(a,b) 함수를 사용하였다.

📌 check() 함수

• 최대 공약수와 최소 공배수를 인자로 받는다.
• 최소 공배수에서 최대 공약수를 나눈 값을 N 에 할당한다.
• 2개의 자연수의 곱이 N 이면서 서로소가 아닌 경우를 찾는다.
• 2개의 자연수의 합이 최소라면 2개의 자연수의 합을 tmpSum 에 할당하고 2개의 자연수에 최대 공약수를 곱한 값을 result 에 할당한다.
• 모든 경우의 확인이 종료되면 result 를 반환한다.

📌 eo(a,b) 함수

• 인자로 받은 두 자연수 a, b 중 작은 값은 MIN 에 큰 값은 MAX 에 할당한다.
• 자연수 2부터 MIN 값 까지 반복문을 실행하여 두 자연수를 나누었을 때 두 자연수가 모두 정확하게 나누어 떨어질 때 현재 두 자연수는 서로소가 아니므로 True 를 반환한다.
• 위의 반복문이 모두 종료되었다면 두 자연수는 서로소이므로 False 를 반환한다.

✍ 코드

from math import sqrt
from sys import stdin
# 숫자 a, b가 서로소인지 확인하는 함수
def eo(a, b):
    MIN, MAX = min(a, b), max(a,b)
    for i in range(2,MIN+1):
        if a%i == 0 and b%i == 0:
            return True
    return False
# 최대 공약수와 최소 공배수의 값을 이용해 합이 최소가 되는 두 자연수를 반환하는 함수
def check(gcm, lcm):
    result = [gcm , lcm]
    tmpSum = 100000000
    N = lcm//gcm # 최소 공배수에서 최대 공약수를 나눈 값
    for num in range(1, int(sqrt(N))+1): # N의 값을 2 자연수의 곱으로 변환
        tmp = N // num
        if N % num != 0 or eo(num, tmp): continue  # N의 값을 2개의 자연수의 곱으로 변환이 불가능 or 2개의 자연수가 서로소가 아닌 경우
        ts = tmp + num # 2개의 자연수의 합
        if  ts < tmpSum: # 2개의 자연수의 합이 최소라면
            tmpSum = ts # 최소값 갱신
            result = [num * gcm, tmp * gcm] # 반환할 2개의 자연수 갱신
    return result

gcm, lcm = map(int,stdin.readline().split())
num1, num2 = check(gcm, lcm)
print(num1, num2)