백준 / 수학 / 17087번 / 숨바꼭질 6 / C++

문제

수빈이는 동생 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값의 최댓값을 출력한다.

예제 입력 1 

3 3

1 7 11

예제 출력 1 

2

예제 입력 2 

3 81

33 105 57

예제 출력 2 

24

예제 입력 3 

1 1

1000000000

예제 출력 3 

999999999

 

#include <iostream>
using namespace std;

int abs(int n) {
	return n > 0 ? n : -n;
}

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	int s; // subin's location
	int d; // distance
	
	cin >> n >> s;
	
	int arr[n]; // distance array
	
	for(int i=0; i<n; i++) {
		int a; // younger's location
		cin >> a;
		
		arr[i] = abs(s - a);
	}
	
	d = arr[0];
	for(int i=0; i<n-1; i++) {
		d = gcd(d, arr[i + 1]);
	}
	
	cout << d;
	
	return 0;
}

---

처음엔 문제이해가 잘 안될수도 있다.

일단 결론부터 말하자면, 수빈이의 위치부터 입력받은 동생들의 위치까지의 차를 각각 구한다음 그것들의 최대공약수를 구해주면된다.

 

문제에서 수빈이의 위치가 X일때 1초뒤에 X+D나 X-D로 걷는다고 했는데, 처음엔 이 D값이 유동적으로 변할 수 있을줄 알아서 생각이 좀 꼬였다.

하지만 몇초를 움직이던 D값은 모든 동생들을 만날때까지 고정이라는 점이 이 문제의 핵심같다.

이거를 이해한다면, 동생들의 위치까지의 차들의 최대공약수를 구하면 된다.

 

예를들어 수빈이가 원점(0)에 있고, 동생 3명의 위치가 각각 -15, 24, 3에 있다고 해보자.

그러면 각각 동생들의 위치까지의 차이는 15, 24, 3 이고 이수들의 최대공약수는 3이다.

결국 수빈이는 1초에 3씩 움직여서 모든 동생들을 만날 수 있는것이다.

그 어떤 다른수로 움직이면 위의 동생들을 절대 만날 수 없을것이다.

 

위 코드를 보면 최대공약수를 구하려면 일단 수빈이와 동생의 거리가 모두 양수여야 하기 때문에,

예를들어 위의 예시에서 0에서 -3까지는 -3만큼 움직여야 하는데 3으로 나타내주어야 최대공약수를 구할 수 있다.

따라서 절댓값을 구하는 함수인 abs를 구현해주었고, 최대공약수를 구하는 함수인 gcd를 구현해주었다.

gcd는 유클리드 호제법을 이용한 최대공약수를 구하는 함수인데, 전 포스팅에 정리해놨으니 참고바란다.

2021.08.01 - [ALGORITHM/백준] - 백준 / 수학 / 2609번 / 최대공약수와 최소공배수 / C++

백준 / 수학 / 2609번 / 최대공약수와 최소공배수 / C++

 

그뒤는 간단하다.

동생들 각각과의 거리를 배열에 저장해주고, 차례로 최대공약수를 구해주면 된다.

a, b, c의 최대공약수를 구하는 방법은 a와 b의 최대공약수를 구하고 구한값과 c의 최대공약수를 구해주면된다.