백준 17087 - 숨바꼭질 6

문제 설명 

 

 

=> 나( S )가 갈 수 있는 곳은  ( S + D ) or ( S - D ) 이다. 

=> 내가 Y에 가기 위해서는 Y-S 의 절대값이 D의 배수가 되어야한다. 

=> 내가 Z에 가기 위해서는 Z-S 의 절대값이 D의 배수가 되어야한다. 

=> 모든 Y-S , Z-S 값들의 최대 공약수를 구하면 된다. 

 

ex ) S : 3
동생들 위치 : 

1

7

11

이 경우 최대공약수를 구해야할 수들은

2

4

8

가 된다. 

 

*** 배열을 사용할 때 잘못된 index에 접근하거나, 0으로 나누는 경우가 없도록 주의해야한다. (런타임 에러)

 

 

 

 

 

#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

long GCD (long A, long B)
{
    while(B!=0)
    {
        long tmp=B;
        B=A%B;
        A=tmp;
    }
    return A;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    long N, S;
    cin >> N >> S;
    
    vector<long> arr(N);
 
    for(long i=0; i< N; i++)
    {
        cin>>arr[i];
        long tmp = S-arr[i];
        if( tmp > 0)
        {
            arr[i] = tmp;
        }
        else{
            arr[i] = -tmp;
        }
    }
    
    for(long i=0; i< N-1; i++)
    {
        arr[i+1]= GCD(arr[i], arr[i+1]);
    }
    
    cout << *(arr.end()-1)<<'\n';
    return 0;
}