이번 문제는 최소공배수에 관한 내용이다. 문제는 다음과 같다.
1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.
그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?
접근
문제의 값이 되는 수를 A라고 하면, A는 10으로 나눠떨어질 것이다. 따라서 A는 10의 배수이며, 같은 이유로 1, 2, 3,… ,20의 배수이기도 하다. 이 들의 공통 배수인 조건을 갖는 수 중에서 가장 작은 수라 했으니 최소공배수이다. 세 수 a, b, c의 최소 공배수에 대해서 살펴보자. 먼저 a와 b의 최소 공배수를 l 이라 하자. 다시 l과 c의 최소 공배수를 m이라 하자. m은 l로 나눠지므로 ㅣ의 약수인 a, b로도 나눠진다. 따라서 일련의 수의 최소공배수를 구하려면 앞에서부터 두 수의 최소 공배수를 구한 다음, 이 최소공배수와 다음 항의 최소 공배수를 구한다. 이 과정을 끝까지 반복하면 모든 수의 최소 공배수를 구할 수 있다.
최소 공배수 구하기
최소공배수를 가장 쉽게 구하는 방법은 유클리드의 호제법을 이용하는 것이다. 유클리드 호제법은 두 수 m, n (단, m > n)의 최대공약수는 m-n과 n의 최대 공약수와 동일하다는 점을 이용하는 것이다. 파이썬 코드로는 다음과 같이 간단히 짤 수 있다.
def gcd(a, b):
if a < b:
return gcd(b, a)
if b is 0:
return a
if a % b is 0:
return b
return gcd(b, a%b)최대 공약수를 구했으니 최소 공배수를 구해보자. 두 수 a, b 의 최대공약수를 g라 하면 이 때의 최소공배수 l은 (a * b / g)로 구해진다. 따라서 답은 다음과 같이 구할 수 있다.
from functools import reduce
def lcm(a, b):
g = gcd(a, b)
return a // g * b
print(reduce(lcm, range(1, 21)))다른 접근
손으로 최소공배수를 구하는 방법이 기억나시는지? 이 알고리듬을 적용하여 계산해보도록 하자.
- 최소공배수를 구할 대상 수를 일렬로 쭉 쓴다.
- 소수 하나를 작은 것부터 골라서 1의 왼쪽 아래에 쓴다. 그리고 각 숫자 아래에는 그 수를 고른 소수로 나눈 몫을 쓴다. 만약 나눠지지 않는다면 해당 수를 그대로 쓴다.
- 2의 시행에서 1개라도 나눠진 수가 있으면 2를 반복한다. 모든 후보를 나눌 수 없다면 다음 소수를 골라서 2를 반복한다.
- 처음 수 중에서가 가장 큰 수보다 작은 모든 소수에 대해서 2, 3을 반복한다.
- 이제
ㄴ모양으로 써진 소수들과 나누고 남은 수들을 모두 곱한다.
이를 그대로 사용해보겠다. 파이썬으로는 한 번 풀어봤으니, 이번에는 Swift로 작성했다.
// 20보다 작은 소수는 따로 계산하지 않아도 뭐....
let primes = [2, 3, 5, 7, 11, 13, 17, 19]
var a = Array(1...20)
var tempA: [Int] = a
let result: [Int] = []
// 각각의 소수로 리스트의 각 숫자를 점차 나눠본다.
for p in primes {
while true {
tempA = a.map{ ($0 % p == 0) ? $0 / p : $0 }
if a == tempA {
break
} else {
result.append(p)
a = tempA
}
}
}
// 남은 수들을 긁어서 곱해본다.
print((result + a).reduce(1, *)) 참고