문제
수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A(1), A(2), ..., A(N)에 있다.
수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.
모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.
입력
첫째 줄에 N(1 ≤ N ≤ 10^5)과 S(1 ≤ S ≤ 10^9)가 주어진다. 둘째 줄에 동생의 위치 A(i)(1 ≤ A(i) ≤ 10^9)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.
출력
가능한 D값의 최댓값을 출력한다.
예제 입력 1
3 3 1 7 11 |
예제 출력 1
2 |
예제 입력 2
3 81 33 105 57 |
예제 출력 2
24 |
예제 입력 3
1 1 1000000000 |
예제 출력 3
999999999 |
더보기
Solution
#include<stdio.h>
#include<stdlib.h>
int gcd(int x,int y)
{
if(x<y)
{
int temp=x;
x=y;
y=temp;
}
while(y!=0)
{
int temp=x%y;
x=y;
y=temp;
}
return x;
}
int abs(int x)
{
return x>0?x:-x;
}
int main(void)
{
int N, *A=NULL, S, D=1000000000;
scanf("%d %d", &N, &S);
A=(int *)malloc(N*sizeof(int));
for(int n=0;n<N;n++)
{
scanf("%d", &A[n]);
D=n==0?abs(S-A[0]):gcd(D, abs(S-A[n]));
if(D==1)
break;
}
printf("%d\n", D);
free(A);
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 2903번: 중앙 이동 알고리즘 (0) | 2020.11.26 |
---|---|
<백준 알고리즘> 12833번: XORXORXOR (0) | 2020.11.26 |
<백준 알고리즘> 16431번: 베시와 데이지 (0) | 2020.11.25 |
<백준 알고리즘> 15439번: Vera and Outfits (0) | 2020.11.25 |
<백준 알고리즘> 4766번: 일반 화학 실험 (0) | 2020.11.25 |