[백준] 17087 숨바꼭질 6

 

나의 위치가 S고 Ai의 위치로 갈 수 있는 최대의 D를 구하는 문제다

그럼 처음 입력 받으면서 Ai들과 S의 입력 차를 넣어두고 최대공약수를 구하면 된다

 

최대 공약수를 구하는건 그냥 N으로 찾을 수 있는데 이걸 이분탐색으로 하고 

정렬해서 풀고 하다가 계속 틀렸다

 

그냥 쉽게 N번 보면되는걸...!

 

어쨌뜬 모든 거리의 차는 x*D의 형태로 나오고 최대공약수 D를 찾으면 되므로

gcd를 사용하자!

 

소스코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int n,s,ans;
vector<int> vt;
 
int gcd(int x,int y){
    if(!y) return x;
    return gcd(y,x%y);
}
 
int main(){
    scanf(" %d %d",&n,&s);
    for(int i=0;i<n;i++){
        int k; scanf(" %d",&k);
        vt.push_back(abs(k-s));
    }
    ans = vt[0];
    for(int i=1;i<vt.size();i++){
        ans = gcd(ans,vt[i]);
    }
    printf("%d\n",ans);
}