해당 해설은 이 문제를 풀 수 있는 가장 보편적인 해설을 바탕으로 작성되었습니다.

문제의 시간복잡도는 O(N)입니다.
stations를 한 번 돌면, 정답이 나올 수 있는 시간복잡도를 의미합니다.

아마 시간초과를 겪어보신분이라면, 배열을 만들어서 하나씩 접근하는 방법을
생각하셨을겁니다.

하지만, 굳이 배열을 만들지 않아도, stations에 접근만 하면, 기지국을 몇 개 설치해야하는지
쉽게 구할 수 있는 방법이 존재합니다.

그러기 위해서는 먼저 알아야 할 것들이 존재합니다.

• 기지국의 전파범위를 수식으로 나타낼 수 있는가?
• 전파가 닿지 않는 구간에 필요한 기지국의 최소 설치 대수를 수식으로 나타낼 수 있는가?

위의 2가지는 이 문제를 풀기 위해서 가장 기초적으로 생각해봐야 할 질문입니다.
해당 질문의 답을 할 수만 있다면, 이 문제를 70퍼센트는 풀었다고 볼 수 있습니다.

먼저 기지국의 전파범위를 수식으로 간단히 나타내봅시다. w라는 매개변수가 한 기지국당 전파범위를 의미합니다.
설치된 기지국의 중심으로 양방향의 범위로 w만큼 떨어진 구간까지 전파가 닿게 됩니다.
여기서,

범위 = 2 * w + 1

이라는 수식이 발생합니다. w만큼의 영향이 가는 전파범위가 양방향으로 2개만큼 존재하므로, 2 * w 가 성립이됩니다.
또한 중심을 포함하면 + 1의 범위가 추가되어 한 기지국의 전파범위는 2 * w + 1 이 됩니다.
그럼, 단방향 전파범위는 얼마일까요?

단방향 전파 범위 = w + 1

위와 같습니다. 단지 양방향에서 단방향이 되었기 때문에, w만 존재합니다. 또한 중심이 사라지는 것은 아니므로 +1은
그대로 유지된다는 사실을 알 수 있습니다.

그 다음은, 전파가 닿지 않는 일정구간에 대한 필요한 기지국의 최소 설치 대수는 어떻게 구해야할까?
전파가 닿지 않는 부분의 구간 길이가 5라고 가정하고 w가 1이라고 가정하자,
기지국의 한개당 범위는 2 * w + 1 이므로 3이 되는 것을 알 수 있다.
하지만, 구간의 길이가 기지국의 전파범위가 커버하지 못하므로 최소 2대는 있어야
구간을 커버할 수가 있다. 우리는 여기서 2대가 필요하다는 연산이 어떻게 나왔는지 알 필요가 있다.

전파가 닿지 않는 부분의 구간을 7, w는 마찬가지로 1이라 가정하면,
한 기지국의 전파범위가 3이므로 2대를 설치하면, 6만큼 길이의 구간을 커버할 수 있다.
하지만, 1이 남으므로, 추가로 한 대 더 설치가 필요하게된다.
여기서 눈치채야한다. 현재 구간을 전파범위로 나눈 값이 정수로 딱 떨어지게 된다면,
그냥 나온 결과의 대수만큼 설치하면 되지만, 뒤에 소수점이 붙었다면, 몇개가 모자르게 된다는 의미가 된다.
이러면 기지국을 잘라서 설치하는 것이 불가능하므로, 그냥 +1을 하여 하나 더 설치해주면 된다.
즉, 연산의 결과에 소수점이 발생하면, 무조건 올림을 하라는 의미와 같게 된다.

의사 코드
if 현재구간의길이 <= 2 * w + 1:
     answer += 1
else:
     answer += 올림(현재구간의길이 / (2 * w + 1) )

위와 같은 방식을 생각해볼 수 있다.

우리는 이제 이 문제를 풀기 위해 필요한 모든 데이터를 취득했다.

stations를 순회하면서 전파가 닿지 않은 부분을 탐색하고 해당 구간의 길이를 계산하여,
위의 조건식에 대입하여 답을 더해주면 끝나는 일이다.

그럼, 전파가 닿지 않는 범위를 어떻게 산출해야할까?
이 문제는 센스있게도 stations배열을 오름차순으로 정렬해서 제공한다.
정렬 할 시간을 아낄 수 있다.

시작은 항상 1부터 이므로 처음에 시작값을 1로 한다.
그 다음 for문으로 stations를 돌면서 end값을 갱신한다.
stations는 기지국의 중심의 위치를 담고 있는 배열이다.
우리는 시작위치부터 전파가 닿지않는 부분까지의 구간을 계산하길 바라므로,
가져온 값에 -w - 1 을 연산하여, 전파가 닿지 않는 부분까지 인덱스를 이동시켜준다.
여기서 왜 w와 1을 빼야하는지 이해가 안간다면, 위로 올라가 해설을 다시 볼 것을 권장한다.

end = stations[i] - w - 1

그 이후에 해당 구간에 전파가 닿지 않은 범위가 존재하는지 판별하는 조건이 필요하게 된다.
end가 start 이상이면 전파가 닿지 않는 부분이 항상 존재하게 된다.
하지만 end가 start의 인덱스값의 미만이라면, 전파가 start위치까지 닿게 되므로,
굳이 기지국을 설치할 필요가 없다고 생각하면 된다.

이 때, 조건은

if end >= start

True일 경우 해당 구간의 길이는,

Length = end - start + 1

가 된다. 길이 연산에 +1이 왜 더해지는지 의문점을 가질 수 있다.
하지만, 백문이 불여일견이다. 직접 구간을 연산해보면 왜 그런지 알게 될 것이다.

길이가 존재한다면, 기지국 설치 최소 대수를 구하여, 답에 더해주기만 하면 된다.

그 다음 for문으로 넘어가기 전에,

start 값을

start = stations[i] + w + 1

로 새로 갱신하여 순차적으로 범위탐색을 이어나가도록 한다.
위의 수식은 단순히 범위를 다음 차례로 하나씩 넘겨준 것이다.
그림으로 그려서 범위를 직접확인해보면 더욱 빠른 이해가 될 것이다.

이로써 우리는 생각보다 어렵지 않게 이 문제를 해결하는 것이 가능해졌다.

이 문제에서 가장 유의해야되는 부분이 for문의 범위가 될 것입니다.
해설에서는 알려드리진 않았지만, 문제를 풀다보면 계속 끝 부분의 범위가 계산되지 않는다는 것을
알게될겁니다. 이를 해결하는 센스도 프로그래밍 기술이 되겠죠.

이 해설은 최적의 결과를 보장하는 완벽한 해설이 아닙니다.
단지, 저의 주관적인 의견이 담긴 해설입니다.
따라서, 논리적인 에러가 발생 할 가능성이 존재합니다.

이 문제를 푸는 앞으로 세상을 이끄는 멋진 프로그래머가 될 여러분들을 위해
도움이 됬으면 하는 바람으로 이 해설을 올립니다.