문제 링크

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

문제 설명

• 1~N에 설치된 기지국이 주어짐
• 기지국의 전파 전달 범위가 주어짐
• 추가로 설치해야 할 기지국 개수 리턴

풀이

• 전파가 닿지 않는 구간을 구함
  • i번째, i+1번째 기지국의 사이 체크
• 구간별 필요 기지국 개수를 구함
  • (구간별 범위) / (한 기지국의 범위) 결과값 올림

코드

import math


def solution(n, stations, w):
    answer = 0
    unreached = get_unreached(n, stations, w)
    for s, e in unreached:
        answer += math.ceil((e - s + 1) / (2 * w + 1))
    return answer


def get_unreached(n, stations, w):
    unreached = []
    # 시작
    e = stations[0] - w - 1
    if 1 <= e:
        unreached.append((1, e))
    # 중간
    for i in range(len(stations)-1):
        s = stations[i] + w + 1
        e = stations[i+1] - w - 1
        if s <= e:
            unreached.append((s, e))
    # 끝
    s = stations[-1] + w + 1
    if s <= n:
        unreached.append((s, n))
    return unreached