[알고리즘 문제 풀이][파이썬] 백준 1934번: 최소공배수

백준 1934 문제 링크: https://www.acmicpc.net/problem/1934

📑 문제 설명

테스트케이스 수와 테스트케이스 수에 따른 자연수 두개가 주어졌을 때, 최소공배수를 구하는 프로그램 작성

입력: 첫째줄에는 테스트케이스 수, 둘째줄부터 두 자연수
출력: 각 테스트케이스에 따른 최소공배수

💡 문제 해결 방법

• 최소공배수의 특성
  n1, n2가 주어졌을 때 두 수의 최대공약수가 gcd라고 가정하면,
  n1 = gcd k1
  n2 = gcd k2
  이다.
  n1, n2의 최대공배수는
  lcm = gcd k1 k2가 된다.

1. 최대공약수 구하기
   두 자연수가 주어졌을 때(n1>n2), 나머지 연산을 활용하여 gcd를 구하기.

2. 1에서 구한 최대공약수와 최소공배수의 특성을 사용하여 최소공배수 구하기

💻 코드

import sys


def lcm(a,b):
    num1 = a
    num2 = b
    if (a<b):
        tmp = a
        a= b
        b= tmp

    while(b!=0):
        n = a%b
        a = b
        b = n

    n1 = num1/a
    n2 = num2/a

    print(round(a*n1*n2))


if __name__ == '__main__':
    n = int(sys.stdin.readline())
    for i in range(n):
        a, b = map(int, sys.stdin.readline().split())
        lcm(a,b)
© 2022 GitHub, Inc.
Terms

💟 추가적으로 알게 된 점