[Algorithm] Programmers :: 기지국 설치

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

프로그래머스

struct Node
{
    int start;
    int end;
};
 
int solution(int n, vector<int> stations, int w)
{
    float answer = 0;
 
    vector<Node> usedFragments;
 
    float prevMax = 0;
 
    for (int i = 0; i < stations.size(); ++i)
    {
        int cur = stations[i];
 
        int start = cur - w < 1 ? 0 : cur - w;
        int end = cur + w > n ? n : cur + w;
 
        usedFragments.push_back({ start,end });
    }
 
    for (int i = 0; i < usedFragments.size(); ++i)
    {
        if (usedFragments[i].start - prevMax > 1) // 1개이상의 조각이 있으면
        {
            float fragmentSize = usedFragments[i].start - prevMax - 1;
 
            if (fragmentSize > 0)
            {
                answer += ceil(fragmentSize / (2 * w + 1));
            }
        }
 
        prevMax = usedFragments[i].end;
    }
 
    if (n - prevMax > 0)
    {
        answer += ceil((n - prevMax) / (2 * w + 1));
    }
 
    return answer;
}

N이 20억이라 당연히 완전탐색처럼 하려하면 안된다.

주어진 stations를 기반으로 기지국이 설치안된 구간의 크기를 구해서 기지국을 몇개 설치해야하는지를 알아야하는 문제이다.

이전에 설치된 범위의 최대값을 계속 들고 있는 상태에서, 현재 기지국 범위의 시작값과의 차를 이용해서 설치안된 구간의 크기를 구하고, 그 크기를 기지국범위만큼 나눠서 설치개수를 구하면 된다.

 

헷갈리지 말아야할 것은, 기지국범위가 4이고 설치안된구간의 크기가 5라면 2개를 설치해야한다는 것이다.

그걸 표현하기위해서 그냥 반올림해서 answer에 누적시켰다.