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

#include <iostream>
#include <vector>
using namespace std;

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    vector<bool> result (n+1, false);
    for(int i=0;i<stations.size();i++){
        for(int j=(-w);j<=w;j++){
            if(stations[i]+j > 0 && stations[i]+j <= n){
                result[stations[i] + j] = true;
            }
        }
    }
    int count = 0;
    for(int i=1;i<=n;i++){
        if(result[i] == false){
            count++;
            result[i] = true;
            if(count == (w + 1) || i == n){
                answer++;
                count = 0;
                i+=w;
            }
            } else{
            if(count > 0){
                answer++;
                count = 0;
                i+=w;
            }
        }
        } 
        return answer;
    }

처음에는 이런식으로 하나씩 비교하면서 코드를 작성해주었는데 정확성은 맞는데 시간초과 때문에 틀렸었다. 그래서 좀 찾아보면서 다시 작성하였다..

#include <iostream>
#include <vector>
using namespace std;

int solution(int n, vector<int> stations, int w){
    int answer = 0;
    int current = 1;
    int range = 2*w + 1;
    
    for(int station: stations){
        int start = station - w;
        int end = station + w;
        if(current < start){
            answer += (start-current + range - 1) / range;
        }
        current = end + 1;
    }
    if(current <=n){
        answer += (n-current + range) / range;
    }
    return answer;
}

현재 시점이 기지국 전파 범위에 들지 않으면 현재 시점부터 전파 범위 시작 전까지의 아파트 수를 이용하여 설치해야 하는 기지국의 수를 구해주었다.