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

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

프로그래머스

---

💡 문제 풀이

DP 관련 문제이다.

 

기지국의 최대 전파 범위는 도달 거리의 × 2 + 1 만큼이다.

기지국을 기준으로 좌우로 범위가 나뉘는데 시작 지점부터 기지국 왼쪽 도달 범위까지 거리에서

최대 전파 범위를 나눠서 올림 처리해주면 필요한 최소 개수를 셀 수 있다.

 

이 방법은 단순히 최소 개수만 구해주면되기 때문에 가능하다.

✔️ 느낀 점

이런 류의 문제가 너무나도 약해서 다른 문제들도 많이 풀어봐야겠다.

💻 코드

from math import ceil

def solution(n, stations, w):
    ans = 0
    W = 2 * w + 1
    
    start = 1
    for s in stations:
        answer += max(ceil((s - w - start) / W), 0)
        start = s + w + 1
        
    if n >= start:
        answer += ceil((n - start + 1) / W)
    
    return ans