백준) 17087 - 숨바꼭질6 (C++)

문제 링크 : https://www.acmicpc.net/problem/17087

문제 설명

---

$S$ = 수빈이의 위치

$D$ = 보폭

$A_n$ = n번째 동생의 위치

$D$씩 이동해서 모든 동생의 위치에 도착할 수 있어야 한다.

문제 풀이

---

D씩 이동해서 모든 위치를 방문할 수 있으려면 D는 이동할 거리들의 최대 공약수가 되어야 한다.

이동할 거리가 D로 나눠져야 해당 위치로 정확히 이동할 수 있기 때문이다.

예) gcd(8, 16, 6) = 2

두 거리의 최대 공약수를 구하고,

그렇게 구한 최대 공약수와 다음 거리의 최대 공약수를 구해가는 방식으로

전체 거리의 최대 공약수를 구할 수 있다.

최대공약수를 구하는 알고리즘인 유클리드 호제법 사용.

https://ko.wikipedia.org/wiki/유클리드_호제법

코드

---

#include <bits/stdc++.h>

using namespace std;

int GCD(int a, int b) // 유클리드 호제법
{
	while (b)
	{
		int r = a % b;
		a = b;
		b = r;
	}

	return a;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, prev, cur, answer;

	cin >> n >> prev >> cur;
	
	answer = abs(prev - cur);

	for (int i = 0; i < n - 1; i++)
	{
		prev = cur;
		cin >> cur;
		answer = GCD(answer, abs(prev - cur));
	}
	
	cout << answer << '\n';
}

Uploaded by N2T