[알고리즘 문제 풀이][파이썬] 백준 1934번: 최소공배수
백준 1934 문제 링크: https://www.acmicpc.net/problem/1934
📑 문제 설명
테스트케이스 수와 테스트케이스 수에 따른 자연수 두개가 주어졌을 때, 최소공배수를 구하는 프로그램 작성
입력: 첫째줄에는 테스트케이스 수, 둘째줄부터 두 자연수
출력: 각 테스트케이스에 따른 최소공배수
💡 문제 해결 방법
- 최소공배수의 특성
n1, n2가 주어졌을 때 두 수의 최대공약수가 gcd라고 가정하면,
n1 = gcd k1
n2 = gcd k2
이다.
n1, n2의 최대공배수는
lcm = gcd k1 k2가 된다.
-
최대공약수 구하기
두 자연수가 주어졌을 때(n1>n2), 나머지 연산을 활용하여 gcd를 구하기. -
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
💟 추가적으로 알게 된 점
Author And Source
이 문제에 관하여([알고리즘 문제 풀이][파이썬] 백준 1934번: 최소공배수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yeomja99/알고리즘-문제-풀이파이썬-백준-1934번-최소공배수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)