[백준/Python] 2485: 가로수

[백준/Python] 2485: 가로수

여러 개의 가로수의 위치가 주어질 때, 가로수들의 간격을 일정하게 하기 위해 몇 개의 가로수를 더 심어야 하는지를 찾는 문제이다.

예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다

가로수들의 간격의 최대공약수를 찾으면 어떤 간격을 선택하여야 일정한 간격을 유지할 수 있는지 찾을 수 있다. 예시에서는 4와 6의 최대공약수인 2의 간격을 선택해야 한다.

그렇다면 필요한 가로수의 수는 어떻게 알 수 있을까? 마지막 가로수의 위치에 첫번째 가로수의 위치를 뺀 것을 최대공약수로 나누고 1을 빼면 첫번째 가로수와 마지막 가로수 사이에 2의 간격으로 몇개의 가로수가 존재해야 하는지 알 수 있다.

예시에서는 5개의 가로수가 필요하다. 그러나 3과 7은 이미 주어졌기 때문에 3개의 가로수만 추가로 주어지면 된다. 따라서 테스트 케이스의 출력은 3이어야 한다.

(참고) gcd 함수는 유클리드 호제법을 통해 최대공약수를 구하는 함수이다.

소스코드

def gcd(m, n):
    while n != 0:
        t = m%n
        m = n
        n = t
    return abs(m)

n = int(input())
arr = []
distance = []
for i in range(n):
    arr.append(int(input()))
    if i != 0:
        distance.append(arr[i]-arr[i-1])

# 간격들의 최대공약수를 구한다.
max_gcd = distance[0]
for i in range(n-2):
    max_gcd = gcd(distance[i+1]-distance[i], max_gcd)

# 첫번째 가로수와 마지막 가로수 사이에 필요한 가로수의 수
result = ((arr[n-1]-arr[0])//max_gcd - 1) - n + 2 
print(result)