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

프로그래머스

 

• 기지국 하나가 커버하는 영역이 W = w x 2 + 1, 전달되지 않는 영역의 크기가 A일 때 
• A % W == 0이면 필요한 기지국의 최소 개수는 A / W, 아니라면 A / W + 1이 됨

• 그림에서 처럼 6,7,8,9 총 4의 크기의 영역이 있고 기지국의 범위가 3이면 4 / 3 + 1 = 2가 됨
• 만약 6, 7, 8 이라면 A / W + 1을 사용하면 3 / 3 + 1 = 2가 되버림
• > A % W == 0이라면 A / W + 1에서 1을 빼줄 필요가 있음

 

위 공식을 통해 모든 영역 커버를 위한 기지국 설치의 최소 개수를 구하면 되지만 아래 2가지를 추가로 고려해야함

• 첫 번째 기지국이 1번 아파트까지 커버하지 못할 때
• 마지막 기지국이 n번 아파트까지 커버하지 못할 때

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

// n = 아파트 개수, stations = 기지국이 설치된 아파트 번호 배열(오름차순 정렬), w = 전파 도달 거리
// 전파가 전달되지 않는 영역에서 모든 영역이 전파를 전달 받으려면 최소 몇 개의 기지국을 설치해야하는가?
// 기지국 하나가 커버할 수 있는 영역은 w x 2 + 1, 이하 W
// 전달되지 않는 영역 하나의 크기를 A라고 할 때 해당 영역을 커버하기 위한 기지국의 최소 개수는
// A / W + 1이 된다. 단, A % W == 0이면 A / W가 된다.
// ex) 커버할 수 있는 영역이 3이고 전달되지 않는 영역 하나의 크기가 3이면 기지국은 하나 필요 => 3 / 3 == 1

int calcStation(int start, int end, int W) {
    int area = end - start + 1;
    
    // 두 기지국이 커버하는 영역이 겹칠 때
    if(area <= 0) return 0;
    // A % W == 0일 때
    else if(area % W == 0) return area / W;
    else return area / W + 1;
}

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    int W = w * 2 + 1;
    
    for(int i = 0; i < stations.size(); i++) {
        // 첫 번째 아파트일 때
        if(!i) {
            // 1번 아파트까지 커버한다면 패스
            if((stations[i] - w) == 0) continue;
            // 1번 아파트까지 커버하지 못한다면
            else answer += calcStation(1, stations[i] - w - 1, W);
        }
        else {
            // 영역 계산
            answer += calcStation(stations[i - 1] + w + 1, stations[i] - w - 1, W);
        }
    }
    
    // 마지막 기지국이 n번 아파트까지 커버하지 못할 때
    if(stations[stations.size() - 1] + w < n)
        answer += calcStation(stations[stations.size() - 1] + w + 1, n, W);
    
    return answer;
}