C# [백준 BAEKJOON] 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값의 최댓값을 출력한다.

 

 

풀이 코드

using System;
using System.Collections.Generic;
using System.Linq;

public partial class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split();
        var num = Int32.Parse(input[1]);

        var list = new List<int>();

        var nums = Console.ReadLine().Split();
        foreach (var i in nums) 
        {
            var n = Int32.Parse(i);
            list.Add(Math.Abs(n - num));
        }

        Console.WriteLine(list.Aggregate(gcd));
    }

    static int gcd(int n, int m)
    {
        while (m > 0)
        {
            var r = n % m;
            n = m;
            m = r;
        }

        return n;
    }
}

 

정리하자면

처음에는 순열로 접근하려고 했는데 중간중간 빠진 부분들이 있어서 순열로는 해결이 불가능했다. 그래서 제공되는 값들에 현재 위치를 뺀 후 그 값들의 최대공약수를 구하는 방법으로 구현했다.