백준 1934번 문제 풀이 - 공부 하는 도비

 

 

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

1934번: 최소공배수

최소 공배수를 구하는 문제입니다. 

제가 예전에 유클리드 호제법에 관한 내용을 포스팅한 적이 있습니다.

 

gcd(greatest common divisor) 즉, 최대 공약수를 구하는 방법은 아래 링크를 확인해주세요.

 

2021.05.21 - [파이썬/프로젝트] - [파이썬] 유클리드 알고리즘(Euclidean Algorithm) - 공부하는 도비

[파이썬] 유클리드 알고리즘(Euclidean Algorithm) - 공부하는 도비

다시, 최소 공배수(lcm)와 최대 공약수(gcd) 개념으로 이 문제를 보면, 

lcm 은 두 수의 곱에서 최대 공약수를 나누어 준 수인걸 알 수 있습니다. ex) lcm = (36 * 60) / 12

 

따라서, gcd 를 먼저 구한 뒤, lcm을 계산해줄게요.

import sys

num = int(input())

for i in range(0, num):
    a, b = map(int, sys.stdin.readline().split())
    c, d = a, b

    q, r = 0, 0 
    while True:
        if a < b:
            a, b = b, a     
        q = a // b
        r = a - (q * b)
        if r == 0:
            gcd = b
            break
        a = b
        b = r
    print((c * d) // gcd)

위의 식으로 gcd를 구한 뒤, lcm을 구할 수도 있지만, 

math 모듈을 import 시켜 간단히 lcm 을 구할 수 도 있습니다.

import math
import sys

num = int(input())
for i in range(0, num):
    a, b = map(int, sys.stdin.readline().split())
    print(a * b // math.gcd(a, b))

확실히 더 깔끔하네요

import math
import sys

num = int(input())
for i in range(0, num):
    a, b = map(int, sys.stdin.readline().split())
    print(math.lcm(a, b))

바로 lcm을 구해볼 수 도 있겠죠?

 

네 이렇게 간단히 문제를 풀어보았습니다.