백준 1934번 (최대공약수와 최소공배수)

T= int(input())
for i in range(T):
    A, B= map(int, input().split())
    if A>=B:
        j=A
        while(True):
            if j%A==0 and j%B==0:
                print(j)
                break
            j=j+1
    else:
        j=B
        while(True):
            if j%A==0 and j%B==0:
                print(j)
                break
            j=j+1

처음에는 입력받은 A, B중에서 큰 수를 찾아 그 수에서 1씩 더하며 공배수인지 찾는 알고리즘을 짰다.

하지만 시간초과를 받게 되어 새로운 방법을 공부해보았다.

 

수학적으로 두 숫자의 최대 공약수는 (둘 중에 작은 수)와 (큰 수에서 작은 수를 나눈 나머지)와의 최대 공약수와 같다고한다. 정확히 말하면 작은 수가 0이 될 때까지 반복해서 최대 공약수를 찾아야 한다. 

 

정답코드는 다음과 같다.

T= int(input())
for i in range(T):
    A, B= map(int, input().split())
    if B>A: 
        A, B= B, A  #B가 A보다 작으면 B와 A를 바꿔준다.
    a, b= A, B  #A, B를 a, b에 복사한다.
    while b!=0: #작은 수가 0이 될 때까지
        a=a%b  #a에 큰 수에서 작은 수를 나눈 나머지를 넣어주고
        a, b= b, a  # a, b를 서로 바꾸어 a에 큰수 b에 작은수를 위치시킨다.
    print(A*B//a)  # 이러면 a가 최대공약수가 되고, 두 수를 곱하고 최대공약수로 나누면 최소공배수가 나온다.

 

**a, b= b, a를 이용하면 서로 자리를 바꿀 수 있다.