[백준] 2485번: 가로수 [c#]

 

각 가로수 사이를 일정한 간격으로 최대한 촘촘하게 체울때의 필요한 나무의 개수를 구하면 된다.

 

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();
 
            int T = int.Parse(reader.ReadLine());
            int[] num = new int[T];
 
            num[0] = int.Parse(reader.ReadLine());
 
            int Tree = 0;
            int[] gap = new int[T];
            int MinGap;
 
            for (int i = 1; i < T; i++)
            {
                num[i] = int.Parse(reader.ReadLine());
                gap[i] = num[i] - num[i - 1];
            }
 
            MinGap = EcA(gap[1], gap[2]);
            for (int j = 2; j < T; j++)
                MinGap = EcA(MinGap, gap[j]);
 
            print.WriteLine((num[T - 1] / MinGap) - (num[0] / MinGap) + 1 - num.Count());
 
        }
        static int EcA(int a, int b)
        {
            if (a > b)
            {
                if ( a % b == 0) { return b; }
                else { return EcA(a, a % b); }
            }
            else
                if ( b % a == 0) { return a; }
                else { return EcA(a, b % a); }
        }
    }
}

 

 

가로수의 좌표를 입력받은 뒤, 각 가로수 사이의 거리를 구한다.

이후 거리 간의 최소공배수를 구해서, 출력을 해주면 된다.