기지국 설치

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

프로그래머스

문제설명:

n개의 배열이 있고 서있는곳부터 -w,+w까지 전파가 닿는 기지국이 주어진다. 전체 전파를 닿게하기위해 추가적으로 기지국을 설치할때 기지국의 최소치를 구하시오

 

소요시간:

30분

난이도3

 

코딩:

def solution(n, stations, w):
	# k-w ~ k ~ k+w
	piv = 0
	ans = 0
	for k in stations:
		#설치되어있는 기지국 전까지 최소한으로설치하기 
		ans += (k-1-w-piv)//(2*w+1)
		if (k-1-w-piv)%(2*w+1):
			ans+=1
		#그 기치국의 오른쪽끝
		piv = k+w
	else:
		#마지막 으로부터 남은곳까지 최소한으로 설치하기
		ans += (n-piv)//(2*w+1)
		if (n-piv)%(2*w+1):
			ans+=1
	return ans

 

문제설명은 예시를 든다면, k가 가령 9이고 w가 2일때 한기지국이 커버할수 있는 길이는 2*w+1 즉 5가 됩니다.

그렇다면 9에 있는 기지국은 7까지 커버가 가능하고, 1부터 6까지에 기지국을 설치해야 함으로, 6을 5로 나눈뒤 나머지가 있다면 추가적으로 +1을 해준것 입니다. 그후 그 9에 있는 기지국은 11까지 커버가 가능하기 때문에 다음 시작지점은 12부터 시작합니다.

또한 마지막에 설치되어있는 기지국에대한 계산이 끝나면 , 마지막 기지국의 영향이 끝나는 지점부터 끝까지 같은 메커니즘으로 반복해줍니다. 

 

다른사람 풀이:

import math
def solution(n, stations, w):
    answer, start = 0, 1
    for c in stations:
        answer += math.ceil(((c - w) - start)/(2 * w + 1))
        start = c + w + 1
    answer += math.ceil((n + 1 - start)/(2 * w + 1))
    return answer

원리는 똑같지만 math.ceil함수를 사용해, 딱떨어지지않는다면 +1이 되는 것을 깔끔하게 구현하였습니다.