[BOJ] 백준 2609 최대공약수와 최소공배수 (Swift)

문제

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

2609번: 최대공약수와 최소공배수

풀이

문제 그대로 최대공약수와 최소공배수를 구하는 문제!
최대공약수는 유클리드 호제법을 사용하면 쉽게 구할 수 있다.
간단하게 설명하면
$gcd(A, 0) = A$
$gcd(B, 0) = B$
$A = B * Q + R$ 이고 $B != 0$이면 $gcd(A, B) = gcd(B, R)$이다.
$Q = A / B$ 가 될 것이고, $R = A % B$이다.

이를 재귀함수로 쉽게 구현할 수 있다.
최대공약수를 구했다면, 최소공배수는 어떻게 구할 수 있을까.

어릴때 수학시간에 배웠던 기억을 되살려서..
최소공배수 = A * B / 최대공약수
를 떠올릴 수 있다.

소스코드

	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let a = input[0], b = input[1]
	func gcd(_ a: Int, _ b: Int) -> Int {
	if b == 0 {
	return a
	} else {
	return gcd(b, a % b)
	}
	}
	func lcm(_ a: Int, _ b: Int) -> Int {
	return a * b / gcd(a, b)
	}
	print(gcd(a, b))
	print(lcm(a, b))

view raw 최대공약수와 최대공배수.swift hosted with ❤ by GitHub

후기

굳이 유클리드 호제법을 사용해서 최대공약수를 구하지 않고 완전탐색으로도 구할 수 있을 것이다.
하지만 더 효율적으로 구하기 위해 유클리드 호제법을 사용함.