백준 17087 숨바꼭질6 c++ 유클리드 호제법

이 문제는

수빈이의 현재 위치와

동생들의 위치사이의 간격끼리의 GCD(최대공약수)를 구하는 문제이다

 

그래서

GCD를 구하는 알고리즘을 잘짜야지 통과가 되는데

I=2부터부터 해당 수 까지 일일히 찾으니

너무 오래걸린다

 

구글링해보니

GCD를 구하는 유명한 알고리즘

유클리드 호제법이라는게 있어서

사용해보았다

 

 

유클리드 호제법이란

수 A,B 가 있을때(A>B)

A%B한 값이 0이 될때까지 반복하면

A값이 최대공약수라는 알고리즘이다

 

증명은 딱히 필요없고

어떻게 그게 되는지 확인해보겠다

A=12, B=8이라 가정

 

First step

A=12, B=8

 

Second step

A=12%8, B=8 -> A=4, B=8 -> A=8, B=4

 

Third step

A=8%4, B=4 -> A=0, B=4 -> A=4, B=0 -> 4가 최대공약수

 

어째서 이렇게 되는지 신기하긴 한데

밑에글을 보면 조금 이해가 된다

 

 

유클리드 호제법에 따르면 a라는 수와 b라는 수가 있을 때 a와 b의 최대공약수(Greatest Common Divisor) gcd(a,b)는 gcd(b, a%b)라고 표현할 수 있다. gcd(a,b)를 a가 b보다 더 크다고 가정하면 q라고 가정했을 때, a = a1*q 로 b = b1*q로 표현 가능하다. 만약 a-b를 하게되면 a-b = (a1-b1)*q가 된다. a1-b1는, a가 b보다 크다고 가정했기 때문에 서로소 관계이고 따라서 a-b는 반드시 a보다 작은 값이 된다. 그리고 가장 중요한 점은 a-b가 q라는 최소공배수를 포함하고 있다는 사실이다.

 

따라서 a와 b의 최대공약수를 구하는 문제가 b와 a-b 사이의 최대공약수배수를 구하는 문제로 치환하여 해결할 수 있다.

 

코드를 살펴보면, a-b가 아니라 a%b로 하였는데 이유는 a-b를 여러번 하는 것과 a%b를 하는 것은 같은 연산이고, 따라서 a%b를 하는 것이 훨씬 빠르기 때문이다. b가 0이 될 때 while문을 빠져나가는데, 이 때 a값이 우리가 구하고자 하는 최대공약수 이다. 수가 모두 소수라면 최대공약수는 1로 출력이 된다.

출처: https://fjvbn2003.tistory.com/37 [Chaos and Order]

 

 

 

내가 이해한대로 설명해 보자면

1. A와 B라는 수가 있다 (A>B) ex)A=144, B=108

 

2. A와 B를 최대공약수의 곱으로 나타낼 수 있다 (A=A1*q, B=B1*q)

144=4*36

108=3*36

 

3. A-B도 최대공약수를 포함한다 

144-08=(4-3)*36     <-36의 배수로 나타내짐

 

4. A-B와 B의 최대공약수를 구하면 된다

B=108  A-B=144-108=(4-3)*36=36

108과 36의 최대공약수배수는 36이다

 

5. A=144, B=108의 최대공약수는 36이다.

 

즉, i=2부터 B까지 일일히 비교해서 최대공약수를 구하는 방식이아닌

A,B -> B, A-B로 반복하여 A-B가 0이될때 B값이 최대공약수라는 것을 알아낸다

그게 가능한 이유는 B와 A-B모두 최대공약수의 곱으로 나타낼 수 있기 때문이다

가끔 A=B가 B보다 큰 경우도 있고, 작은경우도 있는데 적절히 A자리에 큰값, B자리에 작은값이 오게 하면 된다

 

위에서는 108 36이 바로 36이 최대공약수라는 것을 알아냈지만 실제 프로그램은 이렇게 된다

 

A     B  (A>B, A-B와 B로 변환)

144 108

108 36

72 36

36 36

36 0

정답 36

 

 

 

보통 알고리즘을 짜면 뺄셈이아닌 %로하는데 그이유는

뺄셈보다 %이 더 중복된 횟수를 줄여주기때문이다

동일한 알고리즘이다

 

 

 

나의 코드

 

#include <iostream>
#include <math.h>

using namespace std;

int GCD(int, int);

int main() {

	int n, d,temp,fgap,sgap=0;
	cin >> n >> d;

	for (int i = 0; i < n; i++) {
		cin >> temp;
		fgap = abs(temp - d);

		sgap=GCD(fgap, sgap);
	}
	cout << sgap;




	return 0;
}

int GCD(int a, int b) {
	if (b == 0)
		return a;
	else {
		return GCD(b, a % b);
	}
}