C++:: 프로그래머스 < 기지국 설치 >

제한조건의 범위가 상당히 크기 때문에 직접 배열로 생각하면 안되는 문제이다. 간단하게 전파가 필요한 범위를 구해서 최소 몇개의 기지국을 설치해야하는지 계산해 주면 된다.

#include <vector>
using namespace std;

int solution(int n, vector<int> stations, int w) {
    int answer = 0, cur = 1;// 현재 위치
    // n+w+1 에 기지국이 있다 가정( 추가해주지 않는다면 뒷부분이 생략되기 때문에 추가 )
    stations.push_back(n+w+1);
    for (auto& s : stations) {
        int l = s - w, r = s + w;// 기지국에 의한 전파 범위
        if (l > cur) answer += (l-cur-1) / (2*w+1) + 1;// 필요 기지국 개수 계산
        cur = r + 1;// 위치 갱신
    }
    return answer;
}