프로그래머스 : 기지국 설치

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

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

 

해결 방법 : 구현

• 기존에 존재하던 station들의 전파 범위에 벗어나는 구간들을 '거리'로 계산한다.(n이 200,000,000 이하 이므로..)
  • 거리, dist에 최소 몇개의 기지국이 필요한지 계산한다.
• 각 구간들의 최소 기지국 개수를 합산한다.

def solution(n, stations, w):
    answer = []
    
    prev = 1 # 첫번째 아파트
    stations.append(n + 1 + w)
    for s in stations: # 기존 기지국들
        dist = s - prev - w 
        if dist > 0:
            q, r = divmod(dist, 2 * w + 1)
            answer += [q] if r == 0 else [q + 1]
            
        prev = s + 1 + w # s기지국 이후에 전파가 닿지 않는 첫번째 아파트
            
    return sum(answer)