[파이썬 / 백준 1934번] 최소공배수(유클리드 호제법)

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

 

동적계획법을 하다가 너무 막혀서 일단 백준 문제중에 쉬워보이는것 위주로..먼저 풀어보기

기초 알고리즘을 좀 익혀야 심화 문제를 풀 수 있을 것 같아서..(당연)

 

어쨌든 처음에는 그냥 큰 수의 배수를 하나씩 구하면서 작은 수로 나눠지면 출력되게 했는데

시간이 계속 초과되어서 찾아보니 유클리드 호제법이라는게 있었다.

 

유클리드 호제법

: 큰 수를 작은수로 나누어 나온 나머지로 작은 수가 나누어지면 최대공약수를 구할 수 있다.

ex)

45와 27의 최대공약수를 구해야 하는 경우

1) 45%27=18 (공약수가 아님)

2) 27%18=9(공약수가 아님 )

3)18%9=0(공약수는 9)

 

def ul(a,b):
    while True:
        r=a%b
        if r==0: 
            return b
            break
        else: a,b=b,r
    
T=int(input())
for _ in range(T):
    A,B=map(int,input().split())
    mx=ul(max(A,B),min(A,B))
    print(A*B//mx)