백준 문제 풀이 - LCM 5347번

📜 문제 이해하기

두 수 a와 b가 주어졌을 때, a와 b의 최소 공배수를 구하는 프로그램을 작성하시오.

💡 문제 재정의

숫자 두개의 lcm을 구하자.

✏️ 계획 수립

유클리드 호제법을 사용하면 된다.

💻 계획 수행

import sys

# 유클리드 호제법
def get_gcd_lcm(a, b):
    multiply_ab = a * b
    while b > 0:
        a, b = b, a % b
    return a, multiply_ab // a


if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())

    for _ in range(N):
        n, m = map(int, sys.stdin.readline().split())
        dummy, lcm = get_gcd_lcm(n, m)
        print(lcm)

🤔 회고

유클리드 호제법을 사용하면 가볍게 풀 수 있는 문제이다.