[ 프로그래머스 ] 기지국 설치

문제

---

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

풀이

---

현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열 stations, 전파의 도달 거리 W가 매개변수로 주어질 때, 모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값을 구하는 문제로, 단순하게 완전 탐색을 사용 시 시간 초과가 발생한다. 따라서 기지국을 설치할 수 밖에 없는 위치를 파악하고 이를 지워나가면서 문제를 해결한다.

오름차순으로 정렬된 stations의 첫 번째 기지국의 전파 범위가 첫 번째 아파트에 닿지 않는다면 해당 위치에 기지국이 배치되어야 한다. 최소 필요 개수는 ‘설치 필요 범위 / 전파 범위’ 이며, stations의 첫 번째 기지국의 전파 범위가 닿지 않았으므로 같은 범위를 가진 다른 기지국이 간섭할 수 없어, 해당 위치는 최소 기지국 개수를 가진다. 그리고 stations 두 번째 기지국과 첫 번째 기지국 간 전파 범위가 닿지 않는 아파트 존재 시, 첫 번째 기지국의 전파 범위까지는 이미 최소 기지국 개수를 가지므로, 해당 위치에 설치될 최소 필요 개수 또한 최소 기지국 개수를 가진다.

이를 stations의 모든 원소에 순차적으로 적용, 첫 번째 아파트부터 stations의 마지막 전파 범위 내 아파트까지의 최소 필요 개수를 구할 수 있고 stations의 마지막 전파 범위 내 아파트가 마지막 아파트가 아닐 시, 해당 위치 최소 필요 개수를 구하면 모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값을 구할 수 있다.

#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 radioSize = (w * 2) + 1;

    for (int i = 0; i < stations.size(); i++)
    {
        start = min(stations[i] - w, start);
        end = min(stations[i] + w, n);
        answer += (stations[i] - w - start) / radioSize;

        if ((stations[i] - w - start) % radioSize != 0)
        {
            answer += 1;
        }

        start = end + 1;
    }

    if (start <= n)
    {
        answer += (n - start) / radioSize;

        if ((n - start) % radioSize != 0)
        {
            answer += 1;
        }

        else if (start == n)
        {
            answer += 1;
        }

    }

    return answer;
}