• TOC {:toc}

이 글은 백준 온라인 저지의 1934번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.03.25

메모리 시간 코드 길이
28776 KB 4724 ms 247 B 
T = int(input())

for _ in range(T):
    A, B = map(int, input().split())
    s = 1
    for i in range(2, int(min(A, B) + 1)):
        while A % i == 0 and B % i == 0:
            s *= i
            A //= i
            B //= i
    print(s * A * B)

피드백

  • 두 수 중 작은 수까지 모든 정수에 대해 공약수 s를 구해서 풀었는데 코드 효율이 많이 떨어졌다.

참고 답안

import sys
input = sys.stdin.readline

# 최대 공약수를 구하는 함수
def gcd(a, b):
    # 두 값 중 큰 값이 첫 번째 인자(나뉘는 수)로 전달되게 함
    if a < b:
        return gcd(b, a)
    # 재귀 종결조건
    # a가 b로 나누어떨어지는 경우 b가 최대 공약수
    if a % b == 0:
        return b
    # 나누는 수 b와 a를 b로 나눈 나머지에 대해 다시 실행
    return gcd(b, a % b)

T = int(input())
for t in range(T):
    a, b = map(int, input().split())
    # (a, b의 최대 공약수) = a * b / (a, b의 최소 공배수)
    sys.stdout.write(str(int(a * b / gcd(a, b))) + "\n")

아이디어 & 풀이

최소공배수는 유클리드 호제법과 최대공약수를 이용해서 구할 수 있다.

유클리드 호제법을 이용해 최대공약수를 구하는 것은 재귀 함수로 간단히 구현한다.