[기초-종합] ★ 6091 - 함께 문제 푸는 날

6091 - 함께 문제 푸는 날

최소공배수는 어떻게 구할까?

1. 유클리드 호제법

- a* b를 a, b의 최대공약수로 나눈 몫 = 최소 공배수

2. 반복문을 이용한 일반적인 방식

어떠한 수(n)을 각 수들로 나눴을 때 나머지가 모두 0이 될 때가지 반복했을 때 n = 최소 공배수

 

(풀이1) math 라이브러리 gcd()함수 이용

import math

# 최소공배수 구하는 함수
def lcm(a, b):
  return int(a * b / math.gcd(a, b))
  
a, b, c = map(int, input().split())
lcm = (lcm(lcm(a, b), c))

print(lcm)

 

나누기(/)의 반환값은 float형이기 때문에 int로 형변환을 해준 후 lcm()인자로 넣어주어야 한다!

※ 파이썬 3.9 버전부터는 math.gcd의 인수로 여러개가 가능하지만 3.9 미만 버전에서는 2개까지만 허용된다.

 

(풀이2) 반복문을 이용한 일반적인 방식

 

a, b, c = map(int, input().split())
# d = 1
d = max(a, b, c)	# 최대값부터 시작

while (d%a != 0 or d%b != 0 or d%c != 0):
    d += 1
    
print(d)

d = 1 부터 시작해도 상관 없지만 최소 공배수는 이 수들 중 최대값  이상인 값이므로 반복을 줄이기 위해서 a, b, c의 최대값부터 반복문을 시작하도록 하였다.