알고리즘 (PS)/BOJ
[백준] 2485 - 가로수 (S4)
https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 모든 가로수의 간격이 같도록 새로 심어야 하는 가로수의 최소 개수를 구하는 문제이다. (최대 개수로 심으려면 그냥 간격을 1씩 해서 심으면 되니 간단하다) 바꿔말하면 주어진 수열이 등차수열이 되도록 하는 공차의 최댓값을 구하는 문제로 볼 수 있다. 등차수열의 일반항 An = a + (n-1)d 으로 생각을 해보면 구하는게 공차의 최댓값이니 공차를 구하는데 방해가 되는 초항 a 를 없애준다...
