[BOJ][C#] 2485 가로수

📕 문제

📌 링크

📗 접근 방식

1. 각 나무 사이의 간격을 구하여 리스트에 저장
2. 나무 사이의 간격들의 최대공약수를 구함
3. 최대공약수를 기준으로 각 나무 사이의 간격을 나누어 최소한의 나무를 제거하여 최대공약수의 배수로 만듦
4. 최소로 제거해야 하는 나무의 개수를 구함

📘 코드

namespace BOJ
{
    static class Input<T>
    {
        public static T Get() => ConvertTo(Console.ReadLine());
        private static T ConvertTo(string input) => (T)Convert.ChangeType(input, typeof(T));
    }
    
    class No_2485
    {
        static void Main()
        {
            int N = Input<int>.Get();

            List<int> trees = new List<int>();
            List<int> treeDistance = new List<int>();

            for (int i = 0; i < N; i++)
            {
                int tree = Input<int>.Get();

                trees.Add(tree);
            }

            for (int i = 0; i < N - 1; i++)
            {
                int distance = trees[i + 1] - trees[i];
                
                treeDistance.Add(distance);
            }
            
            int count = 0;
            int gcd = treeDistance[0];
            for (int i = 1; i < N - 1; i++)
            {
                gcd = GCD(gcd, treeDistance[i]);
            }
            
            for (int i = 0; i < N - 1; i++) 
            {
                count += (treeDistance[i] / gcd) - 1;	
            }

            Console.WriteLine(count);
        }

        static int GCD(int x, int y)
        {
            int z = x % y;

            return z == 0 ? y : GCD(y, z);
        }
    }
}

📙 오답노트

📒 알고리즘 분류

• 수학
• 정수론
• 유클리드 호제법