기지국 설치 [Lv. 3]

프로그래머스

 N개의 아파트와 stations 만큼의 4G 기지국이 있을 때 4G 기지국을 5G로 바꾸려고 합니다.

5G는 4G보다 범위가 적기 때문에 기지국을 추가로 설치해야합니다.

모든 아파트에서 인터넷을 쓰려면 최소 몇개의 기지국을 추가로 설치해야하는지 찾아주세요

 

풀이 방법

인터넷이 닿지 않는 공간을 계산하면 간단합니다.

// 1 ~ 11
[] [] [] [O] [] [] [] [] [] [] [O]

위와 같이 4번, 11번에 기지국이 설치되어 있고 인터넷 범위가 1이라면

인터넷이 닿지 않는 공간은 아래의 빈칸 입니다. ( O는 인터넷 가능 범위)

[] [] [O] [O] [O] [] [] [] [] [O] [O]

 

첫 번째 빈칸은 2개, 기지국 1개로 커버가 가능합니다.

두 번째 빈칸은 4개, 기지국 2개로 커버가 가능합니다.

즉, 추가로 필요한 기지국은 3개

 

인터넷 범위가 2일 때을 보겠습니다.

[] [O] [O] [O] [O] [O] [] [] [O] [O] [O]

첫 번째 빈칸은 1개, 기지국 1개를 필요로 합니다.

두 번째 빈칸은 2개, 기지국 1개를 필요로 합니다.

즉 추가로 필요한 기지국은 2개입니다.

 

코드로 표현해보자면 

int GetCost(int length, int w)
{
    int ret = length / (w * 2 + 1);
    ret += length % (w * 2 + 1) > 0 ? 1 : 0;
    return ret;
}

위 계산식으로 길이당 필요 기지국을 구할 수 있겠습니다.

 

정답 코드

#include <iostream>
#include <vector>
using namespace std;

int GetCost(int length, int w)
{
    int ret = length / (w * 2 + 1);
    ret += length % (w * 2 + 1) > 0 ? 1 : 0;
    return ret;
}

int solution(int n, vector<int> stations, int w)
{
    int answer  = GetCost((stations[0] - w) - 1, w);

    for (int i  = 1; i  < stations.size(); i++)
    {
        int left = stations[i - 1] + w + 1;
        int right = stations[i] - w - 1;

        // left -> 6, right -> 9일 때 길이는 4
        int length = right - left + 1;
        answer += GetCost(length, w);
    }
    answer += GetCost(n - (stations[stations.size() - 1] + w), w);

    return answer;
}