https://school.programmers.co.kr/learn/courses/30/lessons/12927
아파트의 개수 N, 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열 stations, 전파의 도달 거리 W
모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값
단순하게 탐색을 전부하기에는 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;
}
}