[Baekjoon/백준] 1934번 Python

문제 출처: www.acmicpc.net/problem/1934

1934번: 최소공배수

1. 문제 접근 방식

- 최대 공약수와 최소 공배수와의 관계를 이용하여 계산하였다.

- X = AC, Y=BC 일때, 최대공약수는 C, 최소공배수는 ABC

 

2. 내가 푼 코드

import sys


# 최대공약수 구하기
def GCD(X, Y):
    while(Y):
        X, Y = Y, X % Y
    return X

# 최소공배수 구하기
def LCM(X, Y):
    result = (X*Y) // GCD(X, Y)
    return result


T = int(sys.stdin.readline())

for i in range(T):
    A, B = map(int, sys.stdin.readline().split())
    print(LCM(A, B))

 

3. 결과 및 느낀점

- 성공! 최소공배수를 구하는 함수만을 이용하여 했더니 시간초과가 발생했다. 유클리드 호제법에 대한 숙지가 필요한 문제였다.