[Python] 코딩 도장 - 최소공배수

코딩 도장 사이트의 문제를 직접 풀어본 내용을 정리하여 올립니다.

코딩 도장에서 여러 문제를 확인할 수 있습니다.

난이도 순으로 차근차근 풀어보려 합니다.

---

[문제: 최소공배수] - Lv.1

1부터 10까지의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.

그렇다면 1부터 20까지의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?

(원래 문제 제목은 1부터 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수)

출처: https://codingdojang.com/scode/584?answer_mode=hide

---

[풀이]

여러 시도를 했는데 결국 못 풀었다.

원래는 1부터 20까지 소인수 분해를 통해서 각 소수들의 최대승만 모으는 방식을 생각했다.

예를 들어, 14 = 2^1 x 7^1, 20 = 2^2 x 5^1 이면 2^2 x 5^1 x 7^1 로 출력되게 만들려 하였다.

그래서 dictionary로 소수만 모은 다음에 각 숫자들이 소수별로 나눠지는 횟수를 카운트해서 계산하려 하였다.

어떻게든 구현은 되는데 코드 짜면서도 이건 아닌거 같아서 포기했다.

---

[추천 풀이]

추천 풀이를 보기 전에 이 문제는 결국 1부터 20까지의 최소공배수를 구하는 문제이다.

최소공배수를 구하는 방식은 소인수 분해 등이 있지만 두 개의 수가 있다면 두 수의 곱 / 최대공약수 로 산출이 가능하다.

예를 들어, 30 = 2 x 3 x 5, 36 = 2^2 x 3^2 두 수의 최대공약수는 6 = 2 x 3이다.

최소 공배수는 (2 x 3 x 5) x (2^2 x 3^2) / (2 x 3) = 2^2 x 3^2 x 5로 구할 수 있다.

(사실 결국엔 다 소인수 분해에 따른 정리)

from functools import reduce

# 최대공약수
def gcd(a, b):
    if a < b: a, b = b, a
    while b: a, b = b, a % b
    return a

# x*y/gcd(x, y): (두 수의 곱 / 최대공약수) = 최소공배수
def lcm_range(a, b): 
    return reduce(lambda x, y: x*y/gcd(x, y), range(a, b+1))

print(lcm_range(1, 20))

232792560.0

주석은 내가 이해하려고 달아두었다.

이 분은 최대 공약수를 만드는 함수를 정의하고 reduce()를 이용해서 1부터 20까지 최소공배수를 구해나갔다.

최대공약수나 최소공배수에 대한 개념을 까먹고 어렵게 문제를 접근한 것이 아쉽다.