[BOJ] 백준 2485 가로수 (Swift)

문제

https://www.acmicpc.net/problem/2485

2485번: 가로수

풀이

모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 문제입니다.
어떻게 모두 같은 간격이 되도록 할 수 있을까요?

(4, 8, 10, 14)에 가로수가 심어져있다고 가정하면,
간격은 (4, 2, 4) 가 될 것입니다.

모두 같은 간격을 갖으려면 2가 되겠네요.
(6, 12)에 심어야 모든 가로수가 2의 간격을 갖게 될 것입니다.

그렇다면 간격중 가장 작은 수를 간격으로 사용해야할까요?

(4, 10, 14)에 가로수가 심어져있다고 가정합니다.
간격은 (6, 4)가 될 것입니다.

그렇다면 모두 같은 간격을 갖으려면 4의 간격을 가져야할까요?
(4, 10) 사이에 4의 간격을 갖는 가로수는 심을 수 없습니다.

따라서 간격들 사이의 최대공약수의 간격으로 심어주어야 합니다.
(6, 4)의 최대공약수는 2이므로 모두 같은 간격을 갖으려면 2가 됩니다.

(6, 8, 12)에 총 3개를 심어야 같은 간격을 갖을 수 있습니다.

그렇다면 간격들을 배열에 넣어주고, 간격들의 최대공약수를 구해줍시다.

최대공약수가 구해졌다면 이제 몇개를 심어줘야할지를 찾아야합니다.
가로수가 (4, 10, 14)이고, 모두 같은 간격이 2라면
어떻게 6, 8, 12에 심어주어야 할지 구할수 있을까요?

연속된 가로수들의 간격을 구한 후, 위에 구했던 간격으로 나누어주고 1을 뺴주면 구할 수 있지 않을까요?
(10 - 4) / 2 - 1 = 2,
(14 - 10) / 2 - 1 = 1
총 3개가 나옵니다.

더 효율적으로 구할 수 없을까요?

가장 마지막 가로수와 첫번째 가로수를 빼서 가로수의 길이를 구해줍시다.
가로수의 길이를 구하고, 구했던 간격으로 나누어 준다면 몇개의 가로수가 심어져있는지 구할 수 있지 않을까요?
(14 - 4) / 2 + 1 = 6
(4, 6, 8, 10, 12, 14) = 6개

모두 같은 간격으로 4 - 14의 위치에 가로수를 심으면 6개입니다.
저희가 입력받은 가로수의 위치는 총 3개이므로 더 심어야 할 가로수의 개수는 6 - 3 = 3 개입니다.

심어야 할 가로수의 최소수까지 구할 수 있게 되었습니다!

소스코드

후기

가로수들이 모두 같은 간격을 갖도록 구하는것에 최대공약수를 사용해야겠다는 생각이 떠올라서 풀 수 있었습니다.
심어야할 가로수를 직접 배열에 넣는 방식으로 시도하려다, 실패하였고
모두 같은 간격이 되는 가로수의 배열의 요소의 개수를 구하는 방식으로 접근하는 아이디어를 얻었습니다.