[프로그래머스] 기지국 설치 (python)

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

프로그래머스

 

 

 

일단 그림을 보면 기지국에 따라 공간이 나뉘는 것을 볼 수 있다. w가 2인 경우에 5칸을 기지국 하나가 커버할 수 있다는 뜻이다.

 

이걸 일반화 하면, 기지국에서 나오는 전파의 도달거리 w는 w * 2 + 1 크기 만큼 커버할 수 있다.

 

각 구간 별로 커버하지 못 하는 구간들에 기지국이 몇 개 커버 가능한지 계산해주면 해결할 수 있다.

 

Phase 1

첫 번째 아파트부터 마지막 기지국이 커버하는 곳까지의 기지국 수를 구한다.

 

길이와 커버리지가 주어졌을 때 필요한 기지국 수를 계산하는 식은

$$(length + coverage - 1) \space // \space coverage$$

이다.

 

 

Phase 2

마지막 기지국이 커버하지 못 하는 곳이 있다면 추가해준다.

 

각 Phase 별로 구현된 코드는 아래와 같다.

 

def solution(n, stations, w):
    answer = 0
    coverage = 2 * w + 1

    # Phase 1: [1번 아파트 옥상]부터 [마지막 기지국 커버리지 옥상]까지
    start = 1
    
    for station in stations:
        left, right = station - w, station + w
        
        # 현재 기지국의 왼쪽 범위 바깥에 전파가 미치지 않는 구간이 있다면,
        # 그 구간의 길이를 계산하고 필요한 추가 기지국의 수를 구함
        if start < left: 
            length = left - start
            answer += (length + coverage - 1) // coverage # 필요한 기지국 수 계산 식
        
        # start 초기화
        start = right + 1
    
    # Phase 2: [마지막 기지국 커버리지 옥상]이 커버하지 못 하는 곳이 있다면 추가
    # start가 위에 있는 for문에서 초기화 되므로 바로 n과 비교해도 됨
    if start <= n:
        length = n - start + 1
        answer += (length + coverage - 1) // coverage
    
    return answer

 

 

 

references

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

프로그래머스