[1일 1알고] 기지국 설치

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

프로그래머스

간단하게 그리디로 해결하는 문제입니다.

 

4g -> 5g이런 얘기는 딱히 필요없고 미리 설치되어있는 기지국을 활용해 전파를 전달하면 됩니다.

 

N이 최대 2억이기 때문에 전파가 전달된 각 칸을 모두 계산하는 것은 시간초과가 발생할 것입니다.

 

이를 위해 전파가 도달하지 못하는 칸을 구해 수학적으로 계산하는 방법을 사용합니다.

---

stations는 정렬되어 주어지기 때문에 이를 순회하면서 계산합니다.

 

station이 설치되어있는 위치가 x라면 전파가 시작되는 곳은 x-w, 끝나는 곳은 x+w입니다.

만약에 이전에 전파가 끝난 곳이 a라면 x-w-a만큼의 갭이 있는 것이고 이를 커버하기 위해서는

(gap + cover - 1) / (cover) 만큼의 (cover = 2*w+1) 기지국을 더 설치해야합니다.

 

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

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

    int start = 1;
    int end = n;
    int cover = 2 * w + 1;
    for (auto station : stations)
    {
        end = station - w;
        if (end > n)
            end = n;
        int gap = end - start;
        start = station + w + 1;
        if (gap <= 0)
            continue;
        answer += (gap + cover - 1) / (cover);
    }

    if (start <= n)
    {
        int gap = n - start + 1;
        answer += (gap + cover - 1) / cover;
    }



    return answer;
}

 중요한 것은 끝의 처리 같습니다. 마지막 처리를 for문 밖에서 실수하지 않고 처리해야 합니다.