문제
직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. 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 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르며 가까운 위치에 있는 가로수부터 주어진다.
출력
모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.
예제 입력
4 1 3 7 13
예제 출력
3
아이디어
문제를 풀기 전에 복잡해서 그림을 간단히 그려본 다음 풀이를 시작했다. 문제에 나온 예제 입력처럼 1,3,7,13 위치에 심어진 가로수가 있다고 가정해보자. 
1,3,7,13 위치에 심어져 있으면 위와 같은 그림처럼 나무가 심어져 있을 것이다. 여기서 우리가 알아낼 것은 모든 가로수가 같은 간격으로 심어져 있고 심는 가로수의 수가 최소수를 가져야 된다는 조건이 있다. 
예제에서 조건을 만족하면서 가로수를 심으려면 위 그림과 같이 심으면 조건이 만족한다. 위 그림과 같이 5, 9, 11 3개를 심으면 모든 조건을 만족하면서 정답이다. 여기서 5, 9, 11 3개의 심는 나무 수를 구하는 방법을 알아보자. 일단 나무 사이를 같은 간격으로 심으려면 문제에 있던 1,3,7,13의 위치 사이들의 최대 공약수를 구해야 된다. 첫 번째로 1,3 위치의 사이간격은 3-1=2이고, 두 번째 사이간격 7-3=4이고, 세 번째 사이간격은 13-7=6이다. 사이 간격을 종합하면 2칸, 4칸, 6칸이다. 사이 간격의 최소 공배수가 모든 간격을 같게 만드는 사이 간격이다. 2, 4, 6의 최소 공배수는 2이다. 따라서 모든 나무의 간격이 2칸이면 모든 가로수가 같은 간격이 되도록 심을 수 있다. 이를 바탕으로 코드를 작성했다.
코드
풀이보기(클릭)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys
from math import gcd
n = int(sys.stdin.readline())
a = int(sys.stdin.readline())
arr = []
result = 0
for i in range(n - 1):
num = int(sys.stdin.readline())
arr.append(num - a)
a = num
g = arr[0]
for i in range(1, len(arr)):
g = gcd(g, arr[i])
for i in arr:
result += i // g - 1
print(result)
문제 출처
한국정보올림피아드 지역본선 2010 고등부 2번