[Python]백준 1934번 : 최소공배수

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

1934번: 최소공배수

문제를 풀 떄 어떻게 다가가야 하는 걸까 싶을 때

아래 알고리즘 분류에 유클리드 호제법(난생 첨 들어봄)이 있는 걸 보고 검색해보았다.

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

뭔 소리야의 향연

요약하면

a%b=r →b%r=r'→r%r'=r'' 이렇게 하다가 나머지가 0이 됐을 때의 값이 최대공약수라는 것이다.

최소공배수는 a b 두  숫자가 있으면 이 둘의 최대공약수를 제외한 (a/최대공약수)*b 이기 때문에 그에 맞춰서 코드를 짜봤다

c=int(input())
for i in range(c):
    a,b=map(int,input().split())
    tmp_a=a
    tmp_b=b
    if a<b:
        b=tmp_a
        a=tmp_b
    while True:
        if a%b==0:
            break
        else:
            r=a%b
            a=b
            b=r
    if a/b==a:
        print(tmp_a*tmp_b)
    else:
        print(int(tmp_a*tmp_b/b))

예외로 칠게 조금 있어서 오류와 함께 끙끙거렸다. 맨 아래 else:부분을원래 공통으로해놨는데, 최대공약수가 1인경우는 그.. else:꺼로하면 이상한값이나와서..ㅎ....ㅎ..

쨌든 시간은 156ms가 나왔고 나보다 짧은사람 겁나 많았다ㅎ 꼭 모듈...배운다... 꼭배운다....나만느리다....흑