[Python] 5347 LCM

📌 문제

두 수 a와 b가 주어졌을 때, a와 b의 최소 공배수를 구하는 프로그램을 작성하시오

📌 입력

첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다

📌 출력

각 테스트 케이스에 대해서 입력으로 주어진 두 수의 최소공배수를 출력한다.

📌 문제 풀이

👨‍🏫 접근

최소공배수는 최대공약수를 통해 구할 수 있다.

최대공약수는 둘을 나눌 수 있는 최대한의 공약수로 이 공약수를 사용해서 두 수의 곱을 나누면 최소공배수를 구할 수 있다.

일반적으로 두 개의 수를 곱하면 서로의 공배수가 만들어지는데, 이를 서로 나눌 수 있는 수중에 가장 크고 두 수의 나머지를 만들지 않는 수가 최대공약수이기 때문에 두 수의 곱은 최대공약수로 나눠주면 최대공배수가 나온다.

최대공약수를 찾기 위해 유클리드 호제법을 사용했다.

유클리드 호제법은 최대 공약수를 빠르게 찾을 수 있는 알고리즘이다.

A를 B로 나눈 나머지를 R1이라고 할 때, B를 R1으로 나누고 그 나머지를 R2라고 한다. R1을 R2로 나누고 역시 나머지를 이용해서 R2를 나누는 과정을 반복하다보면 나머지가 없는 상황이 나오는데, 그때의 나누는 수가 최대공약수이다.

A / B = N1 + R1
B / R1 = N2 + R2
R1 / R2 = N3 + R3
R2 / R3 = N4 + R4
...

가로 22, 세로 8인 직사각형을 정사각형으로 나눈다고 할 때, 22 / 8 = 2 + 6, 8 / 6 = 1 + 2, 6 / 2 = 3 + 0으로 최대 공약수는 2이다. 이런 것처럼 수를 가장 작게 쪼개는 느낌이다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
input = sys.stdin.readline

def gcd(n, m):
    tmp = n % m
    while tmp != 0:
        n = m
        m = tmp
        tmp = n % m

    return m

n = int(input())

for _ in range(n):
    a, b = map(int, input().split())
    print(a * b // gcd(a, b))

📄 준비

import sys
input = sys.stdin.readline

📄 풀이

def gcd(n, m):
    tmp = n % m
    while tmp != 0:
        n = m
        m = tmp
        tmp = n % m

    return m

n = int(input())

for _ in range(n):
    a, b = map(int, input().split())
    print(a * b // gcd(a, b))

최대공약수를 먼저 구한다. tmp는 나머지를 위해 만든 변수이다. 이 나머지가 0일 때까지 계속해서 과정을 반복한다.

📌 총평

까먹고 있었는데 다시 외워야겠다.