[백준] 2485 - 가로수 (S4)

https://www.acmicpc.net/problem/2485

2485번: 가로수

모든 가로수의 간격이 같도록 새로 심어야 하는 가로수의 최소 개수를 구하는 문제이다.

(최대 개수로 심으려면 그냥 간격을 1씩 해서 심으면 되니 간단하다)

 

바꿔말하면 주어진 수열이 등차수열이 되도록 하는 공차의 최댓값을 구하는 문제로 볼 수 있다.

등차수열의 일반항 An = a + (n-1)d 으로 생각을 해보면

구하는게 공차의 최댓값이니 공차를 구하는데 방해가 되는 초항 a 를 없애준다.

 

이 문제에 적용하면 주어진 수를 정렬한뒤, 가장 크기가 작은 원소의 값만큼 모든 원소의 값을 빼준다.

그러면 초항이 0인 수열의 등차를 구하는 구하는 문제가 된다.

 

이 과정을 거치고 나면 이 수열을 구성하는 원소는 모두 등차의 배수가 된다.

바꿔말하면 이 등차는 수열을 구성하는 모든 원소의 약수이다.

 

가로수를 최소한으로 심으려면 간격이 커야만 한다.

따라서 이 등차의 값이 최대가 되어야 하므로, 이 수열 원소들의 최대공약수를 구하면 된다.

 

문제의 답을 도출하기 위해서는

주어진 수 중 가장 큰수를 마지막 원소로 하는 등차수열을 구성한다고 생각하면 된다.

구성할 등차수열의 원소 개수 - 이미 주어진 원소 개수를 구하면 문제의 답이 나온다.

 

import sys
input = sys.stdin.readline

def GCD(a, b):
    if b == 0: return a
    return GCD(b, a%b)

n = int(input())
l = [int(input()) for _ in range(n)]
l.sort()
l = list(map(lambda x: x-l[0], l))
g = l[1]
for i in range(2, n):
    g = GCD(g, l[i])
print(l[-1]//g - len(l) + 1)