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

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

17087번: 숨바꼭질 6

 

문제

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.

수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.

모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 105)과 S(1 ≤ S ≤ 109)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 109)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

출력

가능한 D값의 최댓값을 출력한다.

 

풀이

동생위치와 수빈이위치 사이의 거리들을 구하고 해당 거리들의 최솟값을 구하면 된다.

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int getGcd(int a, int b) { // a<b
    int tmp;
    while(a!=0){
        tmp = b%a;
        b = a;
        a = tmp;
    }
    return b;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    int n, s, input;
    cin >> n >> s;
    vector<int> a(n);
    for(int i=0; i<n; i++) {
        cin >> input;
        a[i] = abs(input - s);
    }
    
    int gcd = a[0];
    sort(a.begin(), a.end());
    for(int i=0; i<n; i++)
        gcd = getGcd(gcd, a[i]);
    
    cout << gcd;
    
    return 0;
}

/*
 */