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

https://school.programmers.co.kr/learn/courses/30/lessons/12979

프로그래머스

 

해결 방법

1. 통신이 원활히 되는 right 값을 저장하고있는다. 
2. station을 돌면서, 어디서부터 어디까지 통신이 안되는지를 찾는다. 
3. 그 구간에 기지국이 몇개 필요한지 찾아서 answer에 더해주고, right값을 갱신한다.

 

예제 1로 풀어보기

처음 right = 0 으로 시작한다.  stations[0] = 4이고 w = 1이므로, 3번아파트까지는 통신이 원활하다. 즉, left = 3이다. 

1번~2번아파트에 기지국 설치가 필요하다. 기지국 설치가 필요한 아파트 개수는  right < apt < left 인 apt의 수이다. 따라서 apt 수는 left-right-1 이다. 

 

이 apt 수를 최소기지국을 설치해야한다. 만약 통신범위가 w일경우, 왼쪽으로 w,  오른쪽으로 w, 그리고 자기자신까지 총 2*w+1개의 아파트를 담당할 수 있다. 그러므로 아파트 수를 2w+1 로 나누고 올림처리하면 기지국의 개수가 된다.

 

이제 right값은 station[0] = 4 가 담당할수있는 최대한의 오른쪽값이 된다. 즉, 4+1 = 5가 된다. 이말은, 6번아파트부터는 기지국설치가 필요하다는의미이다. 

 

for문을 완료한 후, 맨 뒤쪽 아파트에 대한 처리도 동일하게 진행한다.

 

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

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;

    int right = 0; //right번까지는 통신가능
    for(int i=0; i<stations.size(); i++){ 
        int left = stations[i]-w; 
        
        int cnt = left-right-1; // right < n <  left //총 기지국 개수
        if(cnt >0){ //통신불가구역
            answer += ceil(1.0f * cnt / (2*w+1));
        }
        
        right = stations[i]+w;
    }
    
    //마지막기지국설치
    if(right <n){
        answer += ceil(1.0f * (n-right)/(2*w+1)); //right < n <= N
    }
    return answer;
}