유클리드호제법 썸네일형 리스트형 [백준 2609] 최대공약수와 최대공배수 (Java) https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 접근 방법 최대 공약수의 경우 유클리드 호제법을 적용하였다. a와 b의 최대 공약수를 구할 때, a와 b 나눠 나머지가 생기면 b와 그 나머지를 다시 나누고 그렇게 생긴 나머지를 처음 나머지와 그 다음 나머지를 다시 나누고.... 나머지가 없을 때까지 나누는데 이 때 나머지가 없을 때의 나눈 값이 최대공약수가 된다. (자세한 내용은 여기) 최소 공배수는 a와 b를 최대공약수로 나누고 그 값들을 곱한 값이 된다. 즉, 최소 공배수 = 최대 공약수 * (a / 최대 공.. 이전 1 다음
