[Programmers] 기지국 설치

기지국 설치

기지국 설치 를 클릭하면 바로 이동한다.

이런 유형의 문제가 제일 어려운 것 같다..

무언가 풀이법을 찾기가 너무 어렵다..

다른 사람의 풀이법을 참조했는데 풀이방법은 맨 왼쪽부터 탐색하면서 전파가 닿지 않는 곳이라면

기지국을 세우고 전파가 닿을 수 있는 가장 멀리 떨어진 곳으로 이동한다.

만약 이미 기지국이 세워져 있는 곳 이라면 그 기지국이 전달하는 가장 먼 곳으로 이동 후 다시 탐색한다.

---

def solution(n, stations, w):
    answer = 0
    idx = 1
    len_stations = len(stations)
    station_idx = 0
    while idx <= n:
        if station_idx < len_stations and stations[station_idx] - w <= idx <= stations[station_idx] + w:
            idx = stations[station_idx] + w + 1
            station_idx += 1
        else:
            answer += 1
            idx += w * 2 + 1

    return answer


if __name__ == "__main__":
    N = 16
    stations = [9]
    W = 2

    print(solution(N, stations, W))