Lv3. 기지국 설치

문제 보기 :  기지국 설치

프로그래머스

 

---

문제

• 정답률 : 55%

---

작성 코드

import math

def solution(n, stations, w):
    answer = 0
    s = stations.pop(0)
    start = s-w ; end = s+w ; l = w*2+1
    answer += math.ceil((start-1)/l)
    
    for i in stations:
        if end < i-w:
            start = i-w 
            answer += math.ceil((start-end-1)/l)
            end = i+w 
        else:
            end = i+w
        
    if end >= n:
        pass
    else:
        answer += math.ceil((n-end)/l)

    return answer

---

풀이

일일히 구한다기 보단, 범위에 따라 기지국을 몇개 설치해야하는지 규칙을 찾는 게 우선인 문제로 읽혔다.

그래서 규칙은, 전파 범위인 w을 활용해, 이미 기지국이 설치된 범위들을 기준으로 start, end를 업데이트하는 식이었다.

어떻게 글로 이걸 설명해야하지

예를 들어, 만약 이미 설치된 첫번째 기지국이 5에 있고 전파 범위가 1이다. 그럼 4는 start, 6이 end가 된다.
그리고 1부터 start 까지는 기지국이 없는 것이니, 4까지 전파가 모두 퍼질 수 있게 기지국을 설치해야하는데 이건 math.ceil로 구했다.
4-1=3 (=len([1,2,3])) 에서 기지국은 1개 설치해야한다. (몇번에 설치했느냐까진 구할 필요없지만 만약 설치했다면 2번이겠지?)

그리고 다음 start가 전단계의 end보다 크다면 start-end-1/(2*w+1)에 반올림을 해서 설치해야하는 기지국 수를 구한다.

추가로 고려해야할 것은 이미 설치된 기지국이 맨 마지막 번호일 경우? 이정도였다.

Lv3치고는 생각보다 간단한 문제인 것 같았다.