[C#] 백준 2485번 가로수

[ 문제 ]

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.

편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.

예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.

심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.

[ 코드 ]

StreamReader input = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter result = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

int n = int.Parse(input.ReadLine());
List<int> numList = new List<int>();
int count = 0;

for (int i = 0; i < n; i++)
{
    int num = int.Parse(input.ReadLine());
    numList.Add(num);
}

int gcd = numList[1] - numList[0];
for (int i = 2; i < n; i++)
{
    int gap = numList[i] - numList[i - 1];
    gcd = GCD(gcd, gap);
}

for (int i = 1; i < n; i++)
{
    int gap = numList[i] - numList[i - 1];
    count += (gap / gcd) - 1;
}

result.Write(count);

input.Close();
result.Close();

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

 

[ 풀이 ]

입력값을 List에 넣은다음에, gcd(최대공약수)를 초기화해준다.

예제 1.

1, 3, 7, 13은 각각 2, 4, 6 만큼의 간격(변수명 gap)이 있는데, 처음 gcd는 최대공약수 2로 초기화됐다.

그 뒤 반복문에서 가로수 gap을 구해 gcd와 gap의 최대공약수를 구한다. (이 예제에서는 초기화된 수가 2이기 때문에 4와 비교해도, 6과 비교해도 계속 최대공약수는 2다.)

그리고 다음 반복문에서는 gap을 gcd로 나눈다음 - 1을 하고 count에 누적시켜준다.

간격을 최대공약수로 나누고 -1하는 이유는 가로수 사이의 간격을 최대공약수로 만들어야하고, 이미 심어져있는 가로수는 제외해야하기때문이다.

최대공약수로 나눈 간격은 1, 2, 3이 되는데,

1과 3을 예시로 들었을때 가로수가 이미 존재하는 위치인 3에는 추가적으로 가로수를 심을 필요가 없으므로 -1을 해주면된다.

따라서 0, 1, 2가 나오고 합을 구하면된다.

 

+ 추가로 가로수를 심어야 할 위치를 찾고 싶을 때는 이 코드를 작성해봤다. 

// 추가로 심어야 할 가로수 위치 찾기
for (int i = 1; i < n; i++)
{
    int gap = numList[i] - numList[i - 1];
    int numCount = (gap / gcd) - 1;
    for (int j = 1; j <= numCount; j++)
    {
        int Position = numList[i - 1] + gcd * j;
        Console.WriteLine(Position);
    }
}

[ 실행화면 ]

case: 1

case: 2

case: 위치찾기

---

문제링크: https://www.acmicpc.net/problem/2485

2485번: 가로수