[백준 1934 파이썬] 최소공배수 (실버5, 정수론)

알고리즘 유형 : 정수론
풀이 참고 없이 스스로 풀었나요? : X

https://www.acmicpc.net/problem/1934

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N = int(input())
for _ in range(N):
    a, b = map(int, input().split())
    num = b
    div = a
    rest = b % a
    while rest != 0:
        num = div
        div = rest
        rest = num % div
    print(a*b // div)

풀이 요약

1. 유클리드 호제법(큰 수를 작은 수로 나눈 나머지 구하는 연산. 나머지가 0이 뜰 때까지, 나누는 수를 나누어지는 수로, 나머지를 나누는 수로 갱신하면서 계속 나머지 구하기, 나머지 0일 때 그 때의 나누는 수가 최대공약수임)

2. 최소공배수 = 두 수의 곱 // 최대 공약수

배운 점, 어려웠던 점

• "최소공배수 = 두 수의 곱 // 최대 공약수" 이걸 몰라서 못 푼 문제였다.