1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.
그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?
접근
1과 20 사이의 모든 수로 나눠지는 수는 1 ~ 20 의 20개의 자연수의 공배수이다. 그 중 가장 작은 수는 결국 20개 수의 최소 공배수를 구하는 문제이다.
세 수 A, B, C의 최소 공배수는 A, B의 최소 공배수를 E 라 할 때, E, C의 최소공배수와 같다. 결국 1~20의 범위에 대해 앞에서부터 두 수의 최소공배수를 누적해서 계산하면 답을 구할 수 있다.
최소 공배수 구하기
두 수 A, B의 최대공약수가 g 일 때, A = a * g, B = b * g 로 표현할 수 있는데, 이 때 두 수 A, B의 최소공배수는 a * b * g 로 계산된다. 즉 최대공약수를 구하면 최대공약수는 간단하게 계산할 수 있다. 최대공약수는 유클리드의 호제법을 이용한 알고리듬이 가장 간단하고 성능도 괜찮은 편이다.
최대 공약수를 구했으니 최소 공배수를 구해보자. 두 수 a, b 의 최대공약수를 g라 하면 이 때의 최소공배수 l은 (a * b / g)로 구해진다. 따라서 답은 다음과 같이 구할 수 있다.
def gcd(a, b):
if a < b:
return gcd(b, a)
q, r = divmod(a, b)
if r == 0:
return b
return gcd(b, r)
def lcm(a, b):
g = gcd(a, b)
return a // g * b
from functools import reduce
def main():
return reduce(lcm, range(1, 21))이 문제에서와 같이 일련의 리스트에 대해서 두 개의 값으로 수행하는 연산을 사용해서 앞의 두 수를 하나의 수로 만들고, 그 결과와 다음 번 수를 반복해서 계산해 나가는 모습이 마치 긴 리스트를 접고 접고 접어서 하나의 값으로 만들어나가는 과정처럼 보인다고 해서 ‘폴드(fold)`라고도 한다. 이러한 폴딩은 파이썬에서는 reduce() 함수를 사용하여 구현할 수 있다. 함수형 언어에서는 이 폴드가 가장 중요한 기본적인 연산 중의 하나이며, 왼쪽에서부터 접거나 오른쪽에서부터 접는 식으로 방향도 구분하여 사용하기도 한다.