문제

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

---

입력

아파트의 개수 N, 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열 stations, 전파의 도달 거리 W

---

출력

모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값

---

풀이

제한조건

• N: 200,000,000 이하의 자연수
• stations의 크기: 10,000 이하의 자연수
• stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다.
• W: 10,000 이하의 자연수

접근방법

단순하게 탐색을 전부하기에는 N의 범위가 매우 크다.
따라서 무작정 탐색을 한다면, 시간초과가 발생한다.

조금 더 문제를 간단하게 생각해보자.

예시와 함께 살펴보자.

기지국이 4에 설치되고 범위가 1이라면 3~5의 범위를 커버할 수 있다. 즉 기지국 설치가 된다면, 2*W+1의 범위만큼을 커버할 수 있다.

그럼 예시에서 봤을때, 4와 11 사이의 커버되지 않는 부분은 6~9 구간으로 총 4개의 지역이 커버되지 않는다.

해당 예시에서는 기지국 설치당 3의 거리를 커버할 수 있으므로 2개의 기지국이 설치된다면 4와 11사이의 모든 범위에 서비스가 가능해진다.

즉 문제를 해결하는 과정을 정리하자면 다음과 같다

1. 각 기지국 사이에 전파가 전달되지 않는 부분의 범위를 구한다.
2. 가장 왼쪽과 가장오른쪽의 전파가 전달되지 않는 부분이 있는지 확인한다.
3. 1-2에서 구한 범위들을 기지국 1개의 커버 범위로 나누며 몇 개의 기지국 설치가 필요한지 확인한다.

이해한것인지 긴가민가 하다면 아래 문제를 풀어보자.
비슷한 문제 https://www.acmicpc.net/problem/2212

---

코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int cover = (2 * w) + 1;
        int virtualLeft = -1 * w;
        int virtualRight = n + w + 1;
        
        for(int i = 1 ; i < stations.length; ++i){
            int value = stations[i] - stations[i - 1] - cover;
            answer += getNeedCount(value, cover);
        }
        answer += getNeedCount(stations[0] - virtualLeft - cover, cover);
        answer += getNeedCount(virtualRight - stations[stations.length - 1] - cover, cover);
        
        return answer;
    }
    public int getNeedCount(int value, int cover){
        int count = 0;
        if(value < 0)
            return 0;
        count += (value / cover);
        if(value % cover > 0)
            count++;
        return count;
    }
}