https://www.acmicpc.net/problem/1934
1934번: 최소공배수
두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있
www.acmicpc.net
소스코드
풀이
★ 최소공배수는 주어진 두 자연수의 곱을 두 자연수의 최대공약수로 나눈 값과 같습니다.
ex) 두 자연수 a,b. 두 수의 최대공약수 r. 최소공배수 => a*b // r
★ 최대공약수를 구하기 위해 유클리드 호제법 알고리즘을 사용해줍니다. 유클리드 호제법은 a와 b의 나머지를 구하는데, 나머지가 0이 되었을 때 두 자연수를 나누는 수가 최대공약수가 됩니다 !
ex) a= 6 b = 10
6 % 10 = 6
10 % 6 = 4
6 % 4 = 2
4 % 2 = 0
=> 최대공약수는 2
★ 위와 같이 두 자연수의 최대공약수를 구했다면, 두 자연수의 곱을 최대공약수로 나눠줍니다. 그 결과값이 최소공배수가 됩니다 :)
★ 유클리드 호제법 참고
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
유클리드 호제법 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란
ko.wikipedia.org
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 1037번: 약수 (Python) (0) | 2023.06.14 |
|---|---|
| [백준 알고리즘] 2609번: 최대공약수와 최소공배수 (Python) (0) | 2023.06.13 |
| [백준 알고리즘] 4153번: 직각삼각형 (Python) (0) | 2023.06.13 |
| [백준 알고리즘] 1259번: 팰린드롬수 (Python) (0) | 2023.06.13 |
| [백준 알고리즘] 2747번: 피보나치 수 (Python) (0) | 2023.06.13 |