728x90
반응형
문제
https://www.acmicpc.net/problem/1934
유클리드 호제법을 이용하여 최소공배수를 구함
유클리드 호제법은 x와 y를 나누었을 때 나온 나머지 r에 대해 x, y의 최대공약수는 y, r의 최대공약수와 같다는 원리
최소공배수는 x * y를 최대공약수로 나눈 몫이 됨
이를 함수로 구현
def gcd(x, y):
while y:
x, y = y, x % y
return x
def lcm(x, y):
return (x * y) // gcd(x, y)
정수 하나를 입력받고 입력한 숫자만큼 두 개의 정수를 입력받아 최소공배수를 구하여 출력
n = int(input())
for _ in range(n):
a, b = list(map(int, input().split()))
print(lcm(a, b))
전체 코드
def gcd(x, y):
while y:
x, y = y, x % y
return x
def lcm(x, y):
return (x * y) // gcd(x, y)
n = int(input())
for _ in range(n):
a, b = list(map(int, input().split()))
print(lcm(a, b))
728x90
반응형
'코딩 > 공부' 카테고리의 다른 글
[Python] 백준 10171번 - 고양이 (0) | 2023.10.10 |
---|---|
[Python] 백준 11382번 - 꼬마 정민 (0) | 2023.10.10 |
[Python] 백준 10039번 - 평균 점수 (0) | 2023.10.10 |
[Python] 백준 2753번 - 윤년 (0) | 2023.10.10 |
[Python] 백준 11653번 - 소인수분해 (1) | 2023.10.10 |