[알고리즘 문제] streetree (Python / 파이썬)

문제

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.
편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.
예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.
심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.  

입력

첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3≤N≤100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 1,000,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르며 가까운 위치에 있는 가로수부터 주어진다.

출력

모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.

---

문제 풀이

이미 심어져 있는 가로수의 위치가 

1 3 7 13 이라고 할 때

-

1 3 은 간격이 2이고 똑같은 간격으로 나무를 심으려면 

1 2 3 (간격 1)

1 3 (간격 2)

두 가지 간격으로 나무를 심을 수 있습니다.

-

3 7 은 간격이 4이고 똑같은 간격으로 나무를 심으려면 

3 4 5 6 7 (간격 1)

3 5 7 (간격 2) 

3 7 (간격 4) 

세 가지 간격으로 나무를 심을 수 있습니다.

-

7 13 은 간격이 6이고 똑같은 간격으로 나무를 심으려면

7 8 9 10 11 12 13 (간격 1)

7 9 11 13 (간격 2)

7 19 13 (간격 3)

7 13 (간격 6)

네 가지 간격으로 나무를 심을 수 있습니다.

-

위의 예로 알 수 있는 것은

어떤 나무 사이에 똑같은 간격으로 나무를 심어야 할 때, 심을 수 있는 간격은

두 나무 사이의 간격의 약수들이라는 것입니다.

따라서 이미 심어져 있는 나무들 사이 사이에 똑같은 간격이 되도록 최소한의

나무를 심으려면 각 나무들 사이 간격의 최대 공약수가 최종 간격이 됩니다.

따라서 각 나무 사이의 간격을 먼저 구하고, 간격들의 최대 공약수를 구해주면 됩니다.

 

나무 사이의 공통 간격을 알았다면 심어야 하는 나무의 개수를 계산할 수 있습니다.

1 3 7 13에서 1과 13의 간격은 12 입니다. 따라서 12를 공통 간격으로 나눠주면 

각 나무 사이의 구간의 개수를 구할 수 있습니다.

따라서 총 나무의 수는 구간의 개수 + 1 이므로 

총 나무의 수를 구해 이미 심어져 있는 나무의 수를 빼주면 최종 답을 구할 수 있습니다. 

---

My Code

# 최대 공약수 구하기
def gcd(a, b):
    while b > 0:
        a, b = b, a % b 
    return a

n = int(input()) # 이미 심어져 있는 가로수의 수

trees = []
for _ in range(n):
    trees.append(int(input())) # 이미 심어진 가로수의 위치

gap = [0] * (n - 1)
for i in range(n - 1):
    gap[i] = trees[i + 1] - trees[i] # 이미 심어진 가로수들 간의 간격

x = gap[0]
for i in range(1, n - 1):
    x = gcd(x, gap[i])    # 간격들의 최대공약수 계산 

# 심어야 하는 가로수의 수 계산
print((trees[-1] - trees[0]) // x + 1 - n)