[백준] 1934번 : 최소공배수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1934번: 최소공배수

 

1. 문제 설명

2. 풀이과정

해당 문제는 두 수의 최소공배수를 구하는 문제인데 최소공배수를 한 번에 구하려고 하다 보니 시간초과가 발생하였다.

하여 유클리드 호제법을 활용하여 두 수의 최대공약수를 구하고 최대공약수와 두 수를 최대공약수로 나눈 값을 곱하여 최소공배수를 구하도록 구현하였다.

유클리드 호제법은 두 수의 최대공약수를 쉽게 구할 때 활용하는데 두 수 중 큰 수를 작은 수로 나누고 생긴 나머지를 이용하여 나누는 수를 나머지로 나누며 나머지가 0이 될 때까지 반복하고 이때 나누는 수가 최대공약수가 된다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 테스트 케이스의 개수를 입력받는다. T = int(sys.stdin.readline())
3. 테스트 케이스 횟수만큼 반복하며 for _ in range(T)
4. 두 정수를 입력받는다. A, B = map(int, sys.stdin.readline().split())
5. 입력받은 두 정수를 비교하여 큰 값과 작은 값으로 구분한다. if (A < B): Min = A  Max = B
6. else: Min = B  Max = A
7. 유클리드 호제법을 활용하며 나머지가 0이 되기 전까지 반복하며 while (Max % Min != 0)
8. 나머지를 저장한다. temp = Max % Min
9. 나누는 수를 나눠지는 수로 바꾸고 Max = Min
10. 나눠지는 수를 나머지로 바꾼다. Min = temp
11. 나머지가 0이 되어 반복문이 종료되었다면 나누는 수가 두 수의 최소공약수가 된다.
12. 최소공약수와 각 수를 최소공약수로 나눈 값을 곱하면 최소공배수가 된다. answer = Min * (A // Min) * (B // Min)
13. 구한 최소공배수를 출력한다. print(answer)

반응형

3. 소스코드

import sys

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

    if (A < B):
        Min = A
        Max = B
    else:
        Min = B
        Max = A

    while (Max % Min != 0):
        temp = Max % Min
        Max = Min
        Min = temp

    answer = Min * (A // Min) * (B // Min)
    print(answer)