백준 BOJ 17087 - 숨바꼭질 6

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

17087번: 숨바꼭질 6

최대공약수를 이용하는 문제.

각 동생의 위치 $A_i$ 에 대해서 수빈이와의 거리 $dir_i$ 를 계산한다.

$dir_i$ 거리를 이동하는 방법으로, 수빈이는 한번에 D만큼만 이동할 수 있기 때문에

$dir_i$ 의 약수가 D이면 수빈이가 동생을 찾을 수 있다.

 

가장 작은 약수는 1이므로 모든 경우에 수빈이는 동생을 찾을 수 있다.

 

각 $dir_i$의 약수들에 대해서 공통인 약수들의 최댓값, 즉 $dir_i$들의 최대공약수를 찾으면

그게 정답이 된다.

 

입력으로 들어오는 N이 1인 경우가 있는데,

이경우에는 최대공약수를 구하지 않고 $dir_0$, 즉 수빈이와 동생 한명의 거리만 출력해주면 된다.

 

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

vector<int> dir; // 수빈이로부터의 거리. 

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

int main(){
	int N,S,k;
	cin >> N >> S;
	for(int i=0; i<N; i++){
		cin >> k;
		dir.push_back(abs(S-k));
	}
	
	if(N == 1){
		cout << dir[0];
		return 0;
	}
	
	int ans = gcd(dir[0], dir[1]);
	for(int i=2; i<N; i++) ans = gcd(ans, dir[i]);
	cout << ans;
	return 0;
}