2485 가로수

임의의 간격으로 세워진 가로수를 더 심어서, 모두 일정한 간격으로 맞추려고 할 때, 심어야 하는 최소한의 갯수를 찾는 문제이다.
간단하게 생각해보면 모든 가로수를 1칸 간격으로 심으면, 두 가로수의 간격 - 1 개의 합으로 계산이 가능하다.
처음에 떠올린것은 가로수의 간격중 최솟값을 찾고, 그 최솟값과 나누어떨어지지 않는 간격이 있으면, 무조건 1개씩 심도록 했는데 오류가 났다.
이유는 최솟값이 4이고 다른 나무의 간격이 6이면 2개씩 심으면 되기 때문이다.
저 케이스를 보고 번뜩 생각난것은 최대공약수였다.
모든 간격과의 최대공약수를 구해서 그 값에 맞게 심으면 된다.

소스