기지국 설치

• n, stations, w, begin
• 아파트단지 토막내기
• 기지국 설치 영역

import sys
sys.setrecursionlimit(10**6)
import math
def solution(n, stations, w, begin = 1):
    if not stations :
        return math.ceil((n-begin+1) / (2*w+1))
    station = stations.pop()
    if station+w >= n :
        return solution(station-w-1, stations, w, begin)
    if station-w <= begin :
        return solution(n, stations, w, station+w+1)
    return solution(station-w-1, stations, w, begin) + solution(n, stations, w, station+w+1)

n, stations, w, begin

재귀함수를 짤때 가장 중요한것은 인자의 뜻을 잘 짜야한다. 무슨 말이냐 하면 이 함수가 이 인자들로 무엇을 하는 함수인지를 잘 인지해야한다. 하노이의 탑 이 풀이를 보고 오면 느낌이 올지도 모른다.

나는 이 함수의 뜻을 이렇게 짰다.

solution(n, stations, w, begin)

• begin 인덱스 아파트부터 시작해서 n 인덱스 아파트에 양옆으로 w크기의 기지국을 설치할껀데, 이미 설치된 아파트는 stations다.

그렇다면 아직 코드 구성을 설명안했지만, 내 코드 중 재귀함수들의 의미만 한번 해석해보자

solution(station-w-1, stations, w, begin)

• begin 인덱스 아파트부터 시작해서 총 station-w-1 인덱스 아파트에 양옆으로 w크기의 기지국을 설치할껀데, 이미 설치된 아파트는 stations`다.

solution(n, stations, w, station+w+1)

• station+w+1 인덱스 아파트부터 시작해서 총 station-w-1 인덱스 아파트에 양옆으로 w크기의 기지국을 설치할껀데, 이미 설치된 아파트는 stations`다.

감좋은 사람들은 알 수 있겠지만, 설치해야하는 아파트 인덱스들이 바뀐다. 알고리즘 원리는 기존에 설치된 stations를 기준으로 남은 아파트를 토막내어 설치가 안된 아파트만 남겨 거기다가 기지국을 설치하겠다라는 알고리즘이다.

아파트단지 토막내기

이미 기지국이 설치되어 전파가 통하는 아파트틀을 때버리고 설치가 안된 아파트갯수에맞게 기지국을 설치하려고한다. 그렇다면 기지국이 설치된 아파트 모양은 이 3가지중 하나일 것이다.

• 가운데에 설치되어 2개으 영역에 기지국을 설치해야하는 경우
• 기지국이 한쪽 끝에있어 한쪽 영역만 기지국을 설치해도되는 경우

기지국을 기준으로 영역을 나눠가며 설치된 기지국이 없어질 때까지 영역을 나눈다.

기지국 설치 영역

\[설치해야하는 기지국 갯수 = \frac{아파트의 갯수}{전파 넓이}\]

math.ceil((n-begin+1) / (2*w+1))

import sys
sys.setrecursionlimit(10**6)
import math
def solution(n, stations, w, begin = 1):
    if not stations :
        return math.ceil((n-begin+1) / (2*w+1))
    station = stations.pop()
    if station+w >= n :
        return solution(station-w-1, stations, w, begin)
    if station-w <= begin :
        return solution(n, stations, w, station+w+1)
    return solution(station-w-1, stations, w, begin) + solution(n, stations, w, station+w+1)