[프로그래머스] Lv3. 기지국 설치

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12979

프로그래머스

코드

from math import ceil
def solution(n, stations, w):
    answer = 0
    dist = 2*w+1
    st = 1
    for i in stations:
        tmp = i-w-st
        if tmp > 0:
            answer += ceil(tmp/dist)
        st = i+w+1
        
    if n >= st:
        answer += ceil((n-st+1)/dist)
    return answer

풀이

• 한개의 기지국이 좌,우 w의 크기만큼 커버하므로 기지국 한개의 설치 범위는 2*w + 1이다.
• stations가 오름차순이므로, 각 스테이션이 커버할 수 없는 위치 (i-w-st)가 0보다 크면 dist로 나눈 몫을 answer에 더해준다. 
  • #1 케이스에서 첫번째 스테이션 원소값에 대한 커버할수 없는 위치는 4-1-1이다.
• 그 후 다음 st는 해당 스테이션의 커버 범위 + 1이어야한다.
• 만약 stations 배열을 다 돌고도 st가 n보다 작거나 같으면, 아직 커버해야할 아파트가 있다는 뜻이므로 거리를 똑같이 구해서 dist로 나눈 몫을 더해준다.