[백준 파이썬] #1934 최소공배수

Silver V

# 1934 최소공배수

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

 

멘토링 Tip

일반적인 풀이로 진행할 경우 런타임 에러가 나도록 의도한 문제이다.

1. 최소공배수는 두 수의 곱을 최대공약수로 나누면 되는 성질 이용
2. 어떻게 하면 최대공야수를 빠르게 구할 것인지 고민

결론적으로 *유클리드 호제법을 사용해 풀이해야 한다

 

유클리드 호제법을 활용한 풀이

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a,b)

 

알게된 점

• 유클리드 호제법 풀이 방식을 암기해두자
• → 함수 정의로 풀이하는 방법, 계산을 통해 출력된 결과값을 다시 활용하는 방법에 익숙해지기

참고 영상

https://youtu.be/R1gxRwXRpMQ