swift ) 백준 2609 최대공약수와 최소공배수 feat.유클리드 호제법

오........

한국정보올림피아드 중고등부에 출제되었던 문제를 만나게 되었다.

물론 1번문제인 걸 보면 쉬운 문제인가보다

나도 응애거릴 때 이 길을 시작했다면 참 좋았을텐데.. 

 

 

먼저 코드를 구현하기 전에

최대공약수(GCD, great common divisor)와 최소공배수(LCM, least common multiple)를 쉽게 구하는 방법을 알아보았다.

 

 

'유클리드 호제법'이라는 것을 이용하려고 하는데

https://myios.tistory.com/11

유클리드 호제법 - 최대공약수, 최소공배수를 구해보자

따로 정리해두었다.

 

이제 위를 바탕으로 코드를 작성해보면....

 

 

// 2609 최대공약수와 최소공배수

let input = readLine()!.split(separator: " ").map{Int(String($0))!}
var a = input.max()!, b = input.min()!

var res = 0
var gcd = 0
var lcm = a * b

while true {
	res = a % b
	if res == 0 {
		gcd = b
		break
	} else {
		a = b
		b = res
	}
}

lcm /= gcd
print(gcd)
print(lcm)