[Level 3] 기지국 설치

https://programmers.co.kr/learn/courses/30/lessons/12979

코딩테스트 연습 - 기지국 설치

---

접근

기지국의 영향을 받지 않는 곳의 크기를 구하고 이를 기지국이 영향을 주는 범위만큼 나눈다. 이제 몫을 올림하여 최종해에 더한다. 기지국의 영향을 받지않는 곳을 봤을 때 (2 * w + 1)로 나누면 필요한 기지국의 개수를 알 수 있다고 판단하였다. 

 

구현

- 먼저 기지국의 범위를 (left, right)의 형태로 ranges에 추가한다.

- 그 다음 ranges를 활용하여 이전의 right값과 현재의 left를 빼서 기지국의 범위에 해당하지 않는 구간을 구한다.

- 구간을 (2 * w + 1)으로 나눠주고 이를 올림하여 answer에 추가한다.

import math
def solution(n, stations, w):
    answer = 0
    ranges = [(0, 0)]
    for s in stations:
        left = s - w if s - w >= 0 else 0
        right = s + w if s + w < n else n
        ranges.append((left, right))
    
    ranges.append((n+1, n+1))
    size = 2 * w + 1
    for i in range(len(ranges) - 1):
        answer += math.ceil((ranges[i+1][0] - (ranges[i][1] + 1)) / size)
    

    return answer