BOJ 2609: 최대공약수와 최대공배수

상당히 직관적이고 간단한 문제이다.

하지만 이 문제를 정확하게 풀려면, (math 모듈을 import 하지 않고ㅡㅡ)

유클리드 호제법을 알아야 한다.

 

유클리드 호제법이란, 'a와 b의 최대공약수'는 'b와 "a를 b로 나눈 나머지"의 최대공약수'와 같음을 나타낸다.

(a를 b로 나눈 나머지를 r라 하곤 한다.)

 

a와 b의 최대공약수 = b와 r의 최대공약수

 

b를 r로 나눈 나머지 r'을 구하고, r을 r'으로 나누고... 계속 반복하면 된다. 

그랬을 때 나머지가 0가 될 때 나누는 수가 바로 최대공약수이다.

 

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

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

여기의 예시에 따르면,

1071과 1029의 최대공약수를 구할때, 

1071%1029==42

1029%42==21

42% 21==0

즉, 21는 최대공약수!

 

이렇게 구하는 것이다.

 

또한 최소공배수는 더욱 간단하게 구할 수 있는데,

두 수를 곱하고 아까 구했던 최대공약수로 나누면 되겠다.

---

본격적인 문제이다.

 

 

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

 

코드는 다음과 같다!

 

 

수학적인 지식을 바탕으로 코딩을 칠 수 있는 것도 꽤나 신기한 경험이다.