백준 C# - 17087 +) 풀이

이 문제를 풀기 앞서 유클리드 호제법에 대해 알아야 한다. 그러므로 밑에 문제를 먼저 푸는 것을 추천한다.

백준 C# - 9613

백준 C# - 9613 +) 풀이 (유클리드 호제법)

---

풀이 

처음에 반복문 두개를 사용해서 풀었는데 시간 초과 결과가 나왔다.

문제에서 X + D나 X - D로 이동할 수 있다. 라는 부분이 있는데 이는 수빈이의 위치와 동생의 위치가 D로 나누어 떨어진다는 의미이다. 여러 동생들 간의 거리를 D로 나누었을때 나머지가 0이되는 최대의 D를 구해야하는데 이것을 해석하면 바로 최대 공약수가 된다.

 

그러므로 우리는 수빈이와 동생들간의 최대 공약수를 구하면 된다.

 

01 유클리드 호제법을 이용한 최대 공약수 메서드

static int GCD(int a, int b)
{
    while (b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

---

02 수빈이와 동생들간의 최대 공약수 구하기

int baseDistance = Math.Abs(s - int.Parse(locations[0]));
for (int i = 1; i < n; i++)
{
    int distance = Math.Abs(s - int.Parse(locations[i]));
    baseDistance = GCD(baseDistance, distance);
}

 

---

예시 문제

3 10
2 18 24

 

1) 첫번째 동생과의 거리를 기준거리로 설정

int baseDistance = Math.Abs(s - int.Parse(locations[0]));

 

2) 순차적으로 나머지 동생들과의 거리와 최대 공약수 계산

for (int i = 1; i < n; i++)
{
    int distance = Math.Abs(s - int.Parse(locations[i]));
    baseDistance = GCD(baseDistance, distance);
}

i = 1 일때 distance = | 10 - 18 | = 8 , baseDistance = GCD(8,8) = 8

i = 2 일때 distance = | 10 - 24 | = 14 baseDistance = GCD(8,14) = 2

3) 그러므로 결과는 2이다.

---

코드 전문

using System;

namespace baek2
{

    class Program
    {
        static int GCD(int a, int b)
        {
            while (b != 0)
            {
                int temp = b;
                b = a % b;
                a = temp;
            }
            return a;
        }

        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();
            int n = int.Parse(input[0]);
            int s = int.Parse(input[1]);
            string[] locations = Console.ReadLine().Split();
            int baseDistance = Math.Abs(s - int.Parse(locations[0]));
            for (int i = 1; i < n; i++)
            {
                int distance = Math.Abs(s - int.Parse(locations[i]));
                baseDistance = GCD(baseDistance, distance);
            }

            Console.Write(baseDistance);
        }
    }
}