Level 3. 기지국 설치

Level 3. 기지국 설치

 

 

전파가 닿지 않는 구간들을 구해, 각 구간을 (2w + 1) 크기씩 채워주면(나누면) 된다.

• 기지국의 번호가 정렬된 상태로 주어지므로, 앞에서부터 구간을 구할 수 있다.

 

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    int start = 1;
    vector<int> section;

    for (int st : stations)
    {
        section.emplace_back(st - w - start);
        start = st + w + 1;
    }

    if (start <= n)
        section.emplace_back(n + 1 - start);

    float W = w + 1 + w;

    for (int sec : section)
        answer += ceil(sec / W);

    return answer;
}