[그리디] 기지국 설치 - Summer/Winter Coding(~2018)

해결 방법

아파트의 개수 N의 범위는 2억까지이기 때문에 O(N) 이상의 시간복잡도로 풀면 시간초과가 나올 것이다.

그래서 범위가 1만까지인 stations 벡터를 이용해서 해결하였다.

 

문제의 접근법은 다음과 같다.

Step 1) 전파가 닿지 않는 연속된 아파트의 길이들을 벡터에 저장한다.

- 예를 들어, 아래 예제의 경우에는 1~2, 6~9 구역에 전파가 닿지 않으므로 2, 4를 벡터에 저장하면 된다.

Step 2) 벡터에 저장된 거리들을 하나씩 꺼내어 각 거리마다 설치할 수 있는 최소 기지국의 수를 합산한다.

- 거리 n에 설치할 수 있는 최소 기지국의 수의 공식은 ceil((float)n/(2*w+1)) (ceil()은 올림 함수)가 된다.

 

 

소스 코드

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

vector<int> dist;
int answer;

int solution(int n, vector<int> stations, int w) {
    // 전파가 닿는 곳 사이의 거리들을 저장
    int p=0;
    for(int i=0;i<stations.size();i++){
        dist.push_back(stations[i]-w-1-p);
        p=stations[i]+w;
    }
    if(p<n) dist.push_back(n-p);
    
    // 최소로 필요한 총 기지국의 수를 구함
    for(int i=0;i<dist.size();i++) answer+=ceil((float)dist[i]/(2*w+1));
    return answer;
}

 

테스트케이스 정확성, 효율성 모두 만점