[BOJ] 백준 1934 최소공배수 (Swift)

문제

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

1934번: 최소공배수

풀이

최소공배수는 어떻게 구할 수 있을까요?

최소공배수는 두 수의 곱 / 최대공약수로 구할 수 있습니다.

그렇다면 최대공약수는 어떻게 구할 수 있을까요?
최대공약수는 소인수분해를 하여 공통된 소수를 찾아서 구할 수도 있겠지만,
유클리드 호제법을 사용하면 더 효율적으로 구현할 수 있습니다.

유클리드 호제법은 나머지를 구하는 연산을 통해 구현하는데,
간단하게 12와 30이 있다고 가정하면

• 30 % 12 = 6
• 12 % 6 = 0

최대공약수(6)를 구할 수 있습니다.

이제 12 * 30 / 6 == 60 최소공배수를 구할 수 있겠죠?

소스코드

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

view raw 최소공배수.swift hosted with ❤ by GitHub

후기

최소공배수 = 두 수의 곱 / 최대공약수 라는 식을 알고,
최대공약수를 구하는 방법을 안다면 쉽게 풀 수 있는 문제입니다.