이번에 풀어본 문제는
프로그래머스 기지국 설치 입니다.

📕 문제 링크

❗️코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;

        int start = 1;
        for (int station: stations) {
            if (start < station - w) {
                answer += getStationCount(start, station - w, w);
            }
            start = station + w + 1;
        }

        if (start <= n) {
            answer += getStationCount(start, n + 1, w);
        }
        return answer;
    }
    static int getStationCount(int start, int end, int w) {
        int notConnectedSize = end - start;

        int stationCount = notConnectedSize / ((w * 2) + 1);
        int remain = notConnectedSize % ((w * 2) + 1);
        stationCount = remain > 0 ? stationCount + 1 : stationCount;

        return stationCount;
    }
}

📝 풀이

각 기지국은 w 만큼의 전파 거리가 된다고 할 때, 주어진 station을 제외하고 모든 아파트에 전파가 닿을 수 있도록 설치할 수 있는 기지국의 최솟값을 반환하는 문제입니다.
효율성을 통과하지 못해서 다른 풀이들을 참고한 결과, 공식이 있었습니다.
전체 구간 / (W * 2) + 1을 해주면 해당 구간에 몇 개의 기지국을 최소로 설치해야 하는지를 구할 수 있습니다. (나머지가 있는 경우 +1)
위 공식을 활용하여 풀이하면 간단하게 해결할 수 있습니다.