Week 1 (수학) - 문제 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값의 최댓값을 출력한다.

 

예제 입력1:

예제 출력1:

코드:

#include<iostream>

using namespace std;

int main()
{
    int N, S;               //입력받을 N과 S
    cin >> N >> S;          //입력 받기

    int* a1 = new int[N];       //동적 배열 생성
    int* a2 = new int[N];       //차를 저장할 동적 배열 생성

    int temp,temp2,rst;                 //중간 변수들과 결과물을 저장할 변수 선언

    for (int i = 0; i < N; i++)         //동생들의 위치 받기
    {
        cin >> a1[i];
    }

    for (int i = 0; i < N; i++)         //동생들의 위치에서의 변위를 a2에 저장
    {
        temp =S - a1[i];
        if (temp < 0)
            temp = -temp;
        a2[i] = temp;
    }
    
    rst = a2[0];                    //a2의 첫 인덱스의 내용물 저장

    for (int i = 1; i < N; i++)             //계산 (차이들의 최대공약수 구하기)
    {
        temp = rst;
        temp2 = a2[i];
        if (temp >= temp2)
        {
            while (temp2 != 0)      
            {
                rst = temp2;       
                temp2 = temp % temp2;      
                temp = rst;       
            }
            rst = temp;
        }
        if (temp < temp2)
        {
            while (temp != 0)
            {
                rst = temp;
                temp = temp2 % temp;
                temp2 = rst;
            }
            rst = temp2;
        }
    }
     
    cout << rst;                    //결과물 출력

    return 0;
}

설명:

주석 참고