BOJ 1934번 : 최소공배수 (Python/수학/Bronze 1)

---

[문제 링크] 👉 https://www.acmicpc.net/problem/1934

---

설명

A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소 공배수라고 한다.
A와 B의 최소공배수를 구하라.

 

풀이

sol.1

for문으로 45000부터 1까지 일일이 검사한다. a와 b를 i로 나눈 나머지가 0일 때 몫을 a와 b에 다시 저장하고 결과값에 i를 곱해 누적한다. for문이 종료되면 a와 b의 곱을 다시 결과값에 곱하며 저장한다. 

 

 

큰 수부터 탐색하는 이유

for i in range(45000, 1, -1):
	if a % i == 0 and b % i == 0:

• 45000부터 1까지 거꾸로 탐색하는 이유는 최대공약수를 가능한 한 빨리 찾기 위함이다. 큰 수부터 시작하면 두 수를 동시에 나누어 떨어지는 가장 큰 공약수를 먼저 찾게 된다.
• a와 b가 i로 나누어 떨어진다면, 이는 i가 두 수의 공약수라는 뜻이며, 이때 가장 큰 값부터 확인하기 때문에 첫 번째로 찾는 값이 바로 최대공약수(GCD)이다.

 

sol.2

두 수의 곱을 그 두 수의 최대공약수(GCD)로 나누면 최대공약수(LCM)가 된다. math 모듈을 이용한다.

import math
math.gcd(a, b)

 

 

 

Solution

sol.1 (반복문 이용)

t = int(input())
for _ in range(t):
    a, b = map(int, input().split())
    result = 1
    for i in range(45000, 1, -1): #45000부터 거꾸로 2까지
        if a % i == 0 and b % i == 0:
            a /= i
            b /= i
            result *= i
    result *= a * b
    print(int(result))

 

📌 몫을 구할 때 '/' 연산자 말고 '//'를 사용하면 int로 변환하지 않아도 된다.

 

 

sol.2 (math모듈 이용)

import math

t = int(input())
for _ in range(t):
    a, b = map(int, input().split())
    result = abs(a * b) // math.gcd(a, b)
    print(result)

 

📌 abs() : 절댓값

 

 

👩‍💻 회고

두 수의 곱을 최대공약수로 나누면 최대공배수가 된다는 걸 이제야 알았다.. 기억해놓자.

그리고 몫을 구할 때 '//'를 사용해야 double형이 아닌 int형으로 반환된다는 것도 알게 됐다.

---