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

문제 요약(본인 해석)

1. 기존에 설치돼있는 기지국들의 위치가 주어집니다.
2. 기지국의 전파 전달거리가 주어집니다.(모든 기지국 공통)
3. 일렬로 늘어져있는 아파트의 개수가 주어집니다.
4. 모든 아파트가 기지국 전파로 이어지려면 몇개의 기지국을 새로 건설해야할까요?

아이디어

산술적으로 비어있는 칸 수를 구한뒤, 이 칸을 매꿀 수 있게끔 기지국을 설치한다.

비어있는 칸 수

아파트촌 시작~0번째 기지국 : d = stations[0]-w-1;
i-1번째 기지국~i번째 기지국 : d = stations[i]-stations[i-1]-1-2*w;
sz-1번째(막) 기지국~아파트촌 끝 : d = n-stations[stations.size()-1]-w;

더하는 기지국 수

if(d>0){
        int added =(d%coverage==0?d/coverage:(d/coverage)+1);
        answer+=added;
    }

음수인 경우 넉넉하게 기지국들 신호들이 겹쳐있다는 거니까 더하지 않는다.

소스

#include <iostream>
#include <vector>
using namespace std;
//산술적 접근
int solution(int n, vector<int> stations, int w){
    int answer = 0;
    int coverage = 2*w+1;
    for(int i = 0;i<stations.size();i++){//자신 기준 왼쪽 공백 매꾸기
        int d;
        if(i ==0 ){
            d = stations[i]-w-1;
        }
        else{
            d = stations[i]-stations[i-1]-1-2*w;
        }
        if(d>0){
            int added =(d%coverage==0?d/coverage:(d/coverage)+1);
            answer+=added;
        }
    }
    //끝부분
    int d = n-stations[stations.size()-1]-w;
    
    if(d>0){
        int added =(d%coverage==0?d/coverage:(d/coverage)+1);
        answer+=added;
    }
    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    //cout << "Hello Cpp" << endl;

    return answer;
}