[백준 / BOJ] C++ 17087 숨바꼭질 6

17087번: 숨바꼭질 6

 

문제

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

17087번: 숨바꼭질 6

 

 

풀이

수빈이는 좌우로 D칸씩 이동할 수 있고 모든 동생을 찾기 위한 D의 최댓값을 찾는 문제다.

즉, 모든 수빈이와 동생 사이의 거리의 최대공약수를 구하는 문제다.

먼저 첫 번째 동생과의 거리를 D라 하자.

다음 동생의 위치를 입력받을 때마다 입력받은 동생과의 거리와 D의 최대공약수를 D에 저장한다.

따라서 D를 출력하면 정답이다.

 

최대공약수를 구하는 방법은 유클리드 호제법을 사용했고

유클리드 호제법에 대해선 아래 링크를 참조하면 좋을 것 같다.

https://khyunx.tistory.com/10

[Algorithm] 최대공약수(GCD), 최소공배수(LCM) - 유클리드 호제법 알고리즘

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL), cout.tie(NULL);
  int n, s, d;
  cin >> n >> s >> d;
  d = abs(s - d);
  for (int i = 1; i < n; i++) {
    int x;
    cin >> x;
    d = gcd(d, abs(s - x));
  }
  cout << d;
  return 0;
}