1934 13241 최소공배수 (python)

백준 단계별로 풀어보기를 하나씩 풀어 보던 중 최대공약수, 최소공배수에 대한 문제를 풀었다. A, B 두 수의 최대공약수를 알면 최소공배수를 구하는 것까지 해결할 수 있다.

두 수를 A, B라고 하고, 최대공약수를 G, 최소공배수를 L이라고 한다면, A와 B를 소인수분해 해서

A = G * a
B = G * b

라는 결과를 얻을 수 있다.

우리는 중학생 시절에 L = G * a * b 라는 사실을 배웠기 때문에….

A * B * / G 정도로 계산하면 된다.

하지만 이때 최대공약수를 계산하는 방법에 문제가 생김…!!!!!

(1934) 최소공배수

문제 🌐

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

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

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

접근 방법

처음에 나는 무식하게 반복문을 돌리려고 했다. 나름대로 머리를 쓴다고 a, b 중 작은 것을 골라내고, 1씩 줄여가며 나머지를 확인하는 반복문을 만들고야 만다.

Full Solution

N = int(input())
for _ in range(N):
    a, b = map(int, input().split())
    A = min(a, b)
    B = max(a, b)
    for i in range(A, 0, -1):
        if B%i== 0 and A%i==0:
            gcd = i
            print(gcd * (A//gcd) * (B//gcd))
            break

채점 기준이 널널한 문제였기 때문에 이런 방법으로 풀어도 크게 문제되지 않았음. 하지만 분수의 덧셈 문제를 풀며 문제에 봉착하게 되고, 최대공약수를 구하는 새로운 방법을 탐색하게 된다…. (이건 다음 기회에)

---

(13241) 최소공배수

여기서도 문제가 발생한다. 위와 같은 방법으로 최대공약수를 구해 보려 했다.

문제 🌐

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

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

정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다.

예:

• 10은 5의 배수이다 (5*2 = 10)
• 10은 10의 배수이다(10*1 = 10)
• 6은 1의 배수이다(1*6 = 6)
• 20은 1, 2, 4,5,10,20의 배수이다.

다른 예:

• 2와 5의 최소공배수는 10이고, 그 이유는 2와 5보다 작은 공배수가 없기 때문이다.
• 10과 20의 최소공배수는 20이다.
• 5와 3의 최소공배수는 15이다.

당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다.

입력

한 줄에 두 정수 A와 B가 공백으로 분리되어 주어진다.

50%의 입력 중 A와 B는 1000(103)보다 작다. 다른 50%의 입력은 1000보다 크고 100000000(108)보다 작다.

추가: 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오. C/C++에서는 long long int를 사용하고, Java에서는 long을 사용하시오.

출력

A와 B의 최소공배수를 한 줄에 출력한다.

접근 방법

이건 문제의 분수 합 문제를 풀다가 발생한 이슈인데, 모두 최대공약수를 이상하게 구해서 나온 결과다…. 그래서 검색을 통해 유클리드 호제법이라는 최대공약수 구하는 방법을 알게 되었다.

유클리드 호제법이란…

내가 이해한 바에 따르면, 두 수 A, B (A>B) 가 있을 때,

A를 B로 나눈 나머지는 두 수의 최대공약수의 배수임을 이용한 방법이다.

간단히 12와 8을 생각해보면, 12는 8로 나누어 떨어지지 않고, 최대공약수는 4이다.

12 = 1*8 + 4
4*3 = 1*(4*1) + 4*1

이때 8, 4에 대해서도 나머지를 확인하며 최대공약수를 찾는다.

while 문을 통해 큰 수를 작은 수로 나눈 나머지를 계속해서 대입한다.

이 동작을 나누어 떨어지지 않을 때까지 반복한다…. 나누어떨어질 때, 자연스럽게 최대공약수가 남게 된다.

def gcd(a, b):
	while b>0:
		a, b = b, a%b
	return a

지금은 이 정도로만 설명할 수 있을 것 같다!! 덕분에 간단하게 최대공약수를 구하고 최소공배수를 계산할 수 있었다.

Full Solution

a, b = map(int, input().split())
def gcd(a, b):
    while b>0:
        a, b = b, a%b
    return a

gcd = gcd(a, b)

print(a*b//gcd)