[백준] 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 이하이다.

출력

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

문제 풀이

이번 문제는 투포인터와 브루트포스로 풀어보았다.

• 입력받은 최소 공배수의 약수 중에서, 입력받은 최대 공약수의 배수인 숫자로 이루어진 배열을 만들었다.
• 그 후 A와 B를 투 포인터로 지정하고, A,B의 최소 공배수가 입력받은 최소 공배수와 같은지 검사한다.
• 이런 식으로 모든 경우를 반복해서 두 수의 합이 최소인 A,B를 구한다.

전체 코드

import math

com_div, com_mul = map(int, input().split())


# com_div의 배수이자, com_mul의 약수인 리스트 반환
def getDivisor(n):
    arr = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            if i % com_div == 0:
                arr.append(i)
            if i ** 2 != n and (n // i) % com_div == 0:
                arr.append(n // i)
    return sorted(arr)


# com_div의 배수이자, com_mul의 약수인 리스트 반환
div_arr = getDivisor(com_mul)

# A, B의 최소 합을 구하기 위해 최대값 설정
minSum = com_mul * 2
A = div_arr[0]
B = div_arr[-1]

# 투 포인터를 사용하여 A와 B 탐색
for i in range(len(div_arr)):
    for j in range(i, len(div_arr) - 1):
        # A와 B의 최소공배수가 com_mul 이라면
        if math.lcm(div_arr[i], div_arr[j]) == com_mul:
            # A+B의 값이 최소인지 확인
            if minSum > div_arr[i] + div_arr[j]:
                A, B = div_arr[i], div_arr[j]
                minSum = A + B
print(A, B)