[백준, 파이썬, 2485번] 가로수

풀이

• 주석에 작성한 것처럼 li에는 가로수 위치
• result에는 가로수 사이의 거리 차이를 넣어주기
• 이후 최대공약수(GCD)를 찾아 해결하는 것을 생각해서
• 처음엔 result를 정렬 후 가장 작은 값과 큰 값의 GCD만을 찾아 적용해봤는데
• 에러가 발생해서 뭔가 설마 모든 경우에 대한 GCD를 찾아야 하는지 고민 후 적용해보니 정답이 나왔다. 
• 처음엔 왜 가장 작은 값과 큰 값의 GCD만 적용하려 했냐면
• 어쨋든 가장 작은 값과 큰 값의 GCD로면 해결이 될 거라고 생각했기에 적용했고, 아직도 반례를 찾지 못해
• 잘은 모르지만 적당히 해결은 했지만... 조금 찝찝하긴하다.

 

import sys
input = sys.stdin.readline

n = int(input())
li = [int(input()) for _ in range(n)] # 가로수 위치
result = [0]*(n-1) # 가로수 거리 차이

for i in range(1,n): result[i-1] = li[i]-li[i-1]

# 최대 공약수
a = result[0]
for i in range(1,len(result)):
    b = result[i]
    while b!=0: a,b = b,a%b

print(sum([i//a-1 for i in result]))