[백준] 1934번 : 최소공배수 (파이썬)

문제

나의 첫번째 답안(시간초과)

import sys
input=sys.stdin.readline
t=int(input())

def mx(num):
    arr=[]
    for i in range(1,num+1):
        if num%i==0:
            arr.append(i)
    return arr

for i in range(t):
    a,b=map(int,input().split())
    arr2=[j for j in mx(a) if j in mx(b)]
    print((a*b)//max(arr2))

해당 풀이는 숫자가 커질수록 계산해야 하는 숫자도 커지게 되므로 시간 초과가 발생할 수 밖에 없는 방법이다.(ex. 45000)

나의 최종 답안

import sys
input=sys.stdin.readline
t=int(input())

def mx(a,b):#최대공약수 구하기
    if b==0:
        return a
    else:
        return mx(b,a%b)

for i in range(t):
    a,b=map(int,input().split())
    print((a*b)//mx(a,b))

접근 방법

• 최소 공배수 문제이므로 유클리드 호제법으로 풀 수 있다.
  해당 개념을 까먹어 어떤 분의 정리글을 참고했다.
• 최소 공배수는 두 수의 곱을 최대 공약수로 나눈 몫으로 구할 수 있으므로, 최대 공약수를 구해주면 된다.
• b가 0이라면 a가 최대 공약수가 되고, 아니라면 약수를 구할 때까지 반복해서 계산해주면 된다(재귀)