Programmers : 기지국 설치

풀이 요약

투포인터?, 그리디라고 해야하나
이분탐색으로도 가능할 듯 싶다.

정확히는 기지국 전파 범위에 포함되지 않는 아파트 범위를 어떻게 찾는 가 이다.

풀이 상세

1. 예를들어 임의의 기지국이 a,b 2개가 있다고 해보자.
2. 우리가 중요시 봐야하는 부분은 a,b 의 전파로 포함되지 않는 아파트의 범위이다. 나의 경우 다음의 3가지를 주시하였다.
   • 전파 범위를 알아야 한다. 아파트 가운데 어떤 아파트는 포함되며 어떤 아파트가 포함되지 않는 지 알기 위함이다. 전파 범위는 $w$ 를 통해 구할 수 있다. $2w+1$
     
   • 기지국을 범위에 포함되지 않는 아파트를 찾아아 한다. 나는 크게 3가지로 나누어 구분했다. 1 ~ 첫 기지국 / 기지국 ~ 기지국 / 마지막 기지국 ~ n
     
   • 기지국끼리 중복되거나 전파 크기보다 인접하여 기지국 범위에 포함되지 않는 아파트가 없는 경우가 존재할 수 있다. 즉 $st, ed$ 를 통해 범위 설정을 할 경우 $st > ed$ 를 넘는 경우가 해당 경우이다. 이 경우는 기지국을 세울 필요가 없으므로 그냥 0 을 반환시키면 된다.

#include <iostream>
#include <vector>
using namespace std;
int sp;
int solve(int st, int ed) {
    if(st>ed) return 0;
    int cnt = ed-st+1;
    return cnt%sp ==0 ? cnt/sp : cnt/sp+1;
}
int solution(int n, vector<int> stations, int w) {
    int answer = 0;
    sp = 2*w+1; // spread -> 전체 전파 값, ex) w=1, sp=3 / w=2, sp=5;
    answer += solve(1,stations.front()-w-1) + solve(stations.back()+w+1,n);
    for(int i=1; i<stations.size(); i++) 
			answer += solve(stations[i-1]+w+1,stations[i]-w-1);
    return answer;
}