[python] 백준 1934번

안녕하세요 !

오늘은 백준 - 최소공배수 문제를 가지고 왔습니다.

문제 설명

해결 방법

이 문제를 유클리드 호제법을 사용해서 문제를 풀었습니다. 아래는 두 수 a, b (a > b)의 최대공약수를 구하는 코드입니다.

def gcd(a, b):
    c = -1
    while 1:
        c = a % b
        if not c:
            return b
        a = b
        b = c

위에서 구한 최대공약수로 최소공배수를 구할 수 있는 방법은 다음과 같습니다.

최소공배수 = a * b / 최대공약수

문제를 해결한 방법을 간단히 정리해보겠습니다.

1. 숫자의 개수를 입력받는다.
2. 두 수를 입력받고 최대공약수를 구해준다.
3. 최소공배수를 출력한다.

1. 숫자의 개수를 입력받는다.

n = int(sys.stdin.readline().strip())

2. 두 수를 입력받고 최대공약수를 구해준다.

for i in range(n):
    arr = list(map(int, sys.stdin.readline().strip().split()))
    if arr[0] >= arr[1]:
        number = gcd(arr[0], arr[1])
    else:
        number = gcd(arr[1], arr[0])

3. 최소공배수를 출력한다.

print(arr[0]*arr[1]//number)

전체 코드

import sys

def gcd(a, b):
    c = -1
    while 1:
        c = a % b
        if not c:
            return b
        a = b
        b = c

n = int(sys.stdin.readline().strip())

for i in range(n):
    arr = list(map(int, sys.stdin.readline().strip().split()))
    if arr[0] >= arr[1]:
        number = gcd(arr[0], arr[1])
    else:
        number = gcd(arr[1], arr[0])
    
    print(arr[0]*arr[1]//number)