[Python] 2485. 가로수

문제

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. 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 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르고, N개의 가로수는 기준점으로부터 떨어진 거리가 가까운 순서대로 주어진다.

출력

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

예제 입력 1 

4
1
3
7
13

예제 출력 1 

3

예제 입력 2 

4
2
6
12
18

예제 출력 2 

5

---

문제를 간단히 이해하자면, 각 가로수들의 거리 간의 최대공약수를 구하여 그 거리만큼 나무를 심는다는 뜻이다.

그리고 심을 나무의 개수는 가로수 사이의 거리를 최대공약수로 나눈 값에 1 을 빼서 구할 수 있다. 

예를 들어,

1, 3, 7, 13 의 위치에 있는 가로수들의 거리 차이는

2, 4, 6 이다. 모든 차이의 최대공약수는 2 이고, 그렇다면 가로수를 2 만큼의 거리를 두고 심으면 된다는 뜻이다.

조금만 더 상세히 설명하자면, 이미 2 만큼의 거리가 차이나는 곳엔 0 개를, 4 만큼 차이난다면 사이에 1 개를 심으면 된다는 말이다.

이는, 거리의 차이를 최대공약수로 나눈 몫에 1 을 뺀 값과 동일하다.

 

먼저, 거리의 차이를 구한다. 문제에서 크기를 정렬해서 주었기 때문에 이를 배열에 담아 정리할 수 있다.

sub = []
for i in range(N-1):
    s = tree[i + 1] - tree[i]  # tree는 입력값을 받아서 만든 배열이다
    sub.append(s)

그리고 거리 차이들의 최대공약수를 구한다.

def Euclidean(a, b):		# math 라이브러리를 사용해도 되지만, 유클리드 호제법을 사용하였다.
    if b == 0:
        return a
    return Euclidean(b, a % b)
    
gcd = sub[0]
for j in range(1, len(sub)):
    gcd = Euclidean(gcd, sub[j])

마지막으로, 심을 나무의 개수를 구하면 된다. 아래는 최종 코드이다.

import sys

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

N = int(sys.stdin.readline())

tree = []
sub = []
cnt = 0
for _ in range(N):
    n = int(sys.stdin.readline())
    tree.append(n)

for i in range(N-1):
    s = tree[i + 1] - tree[i]
    sub.append(s)

gcd = sub[0]
for j in range(1, len(sub)):
    gcd = Euclidean(gcd, sub[j])

for k in sub:
    cnt += (k // gcd) - 1
print(cnt)