백준 2485번 가로수

정답 :

TMI : 갑자기 어려운 문제..

해당 문제를 보고 처음으로 생각한 것으로는, 두 수 사이의 간격을 이용하는 것이였다.

 

간격이 2가 될 수도 있고, 3이 될수도 있고, 4가 될수도 있기에, 그 간격을 구하는 것이 어려웠다.

 

그래서 인터넷을 찾아보던 중 , 간격들의 최대공약수를 이용하여 간격을 구하고,

 

가장 작은 수와 큰 수의 차를 간격으로 나누고 1을 더하면 가로수의 총 개수가 나온다.

 

하지만, 우리는 가로수의 총 개수가 아닌, 가로수의 추가 개수이므로, n을 빼주면 된다.