문제이해
N개의 아파트가 있고 stations배열의 아파트에 기지국이 설치되있을때
기지국설치위치의 +W,-W까지 전파가 퍼진다
모든아파트가 전파가 퍼지도록 하는 기지국을 세울때 최솟값 기지국 개수
1.1번아파트 부터 차례로 검사한다 <= N
2. 기지국이 설치된 아파트의 -W의 위치거나 그이상일때
3. 현재 위치를 바꿔주기 location = stations[idx] + W +1 , idx도 하나 증가시키고
4. 기지국의 범위가 아니라면 설치했다치고 그설치위치에서 최대의 범위 고려하고 +1 위치로 이동하기
def solution(N,stations,W):
answer = 0 # 기지국의 개수
# 1번아파트부터 검사함 현재 아파트위치
location = 1
idx = 0 # 현재기지국을 나타내는 stations의 인덱스
while location <= N:
if idx < len(stations) and location >= stations[idx] - W :
location = stations[idx] + W +1
idx += 1
else:
location += 2*W +1
answer += 1
return answer
N = 11 # 아파트개수
stations = [4,11] # 현재 기지국이 설치되있음
W = 1 # 이만큼 양옆으로 퍼짐
# 모든 아파트에 다 전파가 전달되도록 최소로 기지국을 세울때 기지국의 최솟값 리턴
print(solution(N,stations,W))
idx < len(stations) and location >= stations[idx] - W
순서 다르면 틀림.. 앞의 조건을 만족할때 뒤의 조건을 확인하므로
