문제 설명

전체 코드

def solution(n, stations, w):
    answer = 0
    idx = 0
    locate = 1

    while locate <= n:
        if idx < len(stations) and locate >= stations[idx]-w:
            locate = stations[idx] + w + 1
            idx += 1
        else:
            locate += 2*w+1
            answer += 1

    return answer

해결 방법

문제의 요점은 모든영역을 커버하는 기지국을 최소로 설치하는 것이다. locate를 하나 정하고 stations의 값을 기준으로 0번째 인덱스부터 locate >= stations[idx]-w 이라면 locate = stations[idx]+w+1 만큼 이동해주고 인덱스를 증가시켜준다. 그것이 아니라면 기지국이 가질 수 있는 최대 영역(2*w+1)만큼 현재 위치를 이동시키고 기지국의 갯수를 증가시킨다. 그후 그렇게 나온 결과인 answer을 return 시킨다.