기지국 설치 - level3 (winter/summer coding)

import math

def solution(n, stations, w):
    answer = 0
    dist = []  # 전파 전달 안되는 구간 길이 저장할 리스트
    for i in range(1, len(stations)):
        dist.append((stations[i]-w-1)-(stations[i-1]+w))
    
    dist.append(stations[0]-w-1)  # 맨앞
    dist.append(n-(stations[-1]+w))  # 맨뒤
    
    for i in dist:
        if i <= 0:
            continue
        else:
            answer += math.ceil(i/(2*w+1))  # 올림
    return answer

 

생각을 잘해야되는 게 나는 무조건 배열 형식으로 나눠서 이 문제를 풀려고 했는데 길이에 맞게 필요한 범위만 구하면 되는 문제였다.

 

접근 방식 자체가 틀린 건 아니지만 생각은 많이 엇나갔다.

 

범위와 관련된 문제가 나올 때 이 divide&conquer 식의 접근을 잘 생각해서 접근해야겠다.

 

마지막 수식은 w의 길이 2배만큼 + 1이 기지국을 설치했을때 범위이고 해당하는 범위와 계산된 결과로 나온 값을 올림으로 나온 값이 설치해야하는 기지국의 개수이다.

 

예를 들어 범위가 5고 길이가 6이 나왔다면 1.2라는 값이 나오는데 이는 2개의 기지국이 필요하다는 뜻이다.