[프로그래머스] level 3 - 기지국 설치

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

코딩테스트 연습 - 기지국 설치 | 프로그래머스

 본 문제는 아파트 옥상에 있는 4g 기지국을 5g 기지국으로 바꾸려고 한다. 5g 기지국은 4g의 기지국보다 전달 범위가 좁아 기지국을 추가 설치해야 한다. n개의 아파트가 일렬로 있을 때, 설치해야 하는 기지국의 최소 개수를 구하는 문제다. 

기존의 기지국이 4, 11에 있고 전파의 범위는 1인 경우

 

1, 7, 9에 3개의 기지국을 추가로 설치하면 문제 해결

n의 크기가 200,000,000(2억)이므로 계산량이 너무 많다. 또 기존의 기지국도 10,000개다. 따라서, 기지국을 설치할 수 있는 모든 경우를 만들고, 전파가 잘 되는 경우 중 최솟값을 return 하는 방법은 사용할 수 없다. 그나마 다행인 게 기지국 설치를 최소로 하는 위치를 구하는 문제가 아니기 때문에 전파가 안 되는 부분에 기지국을 추가로 설치하는 방법을 선택했다. 문제 해결 과정은 다음과 같다.

1. 기존에 설치된 1번 째 기지국 왼쪽에 추가 설치해야 하는 개수
2. 기존에 설치된 기지국과 기지국 사이에 추가로 설치해야 하는 개수
3. 기존에 설치된 마지막 기지국 오른쪽에 추가로 설치해야 하는 개수

를 구하면 해결된다. 이때, 혹시 모를 범위의 실수를 해결하기 위해 추가로 설치해야하는 기지국 개수는 0개 부터 시작한다.

#include <iostream>
#include <vector>
using namespace std;
 
int cal(int start, int end, int w) {
    // 전파가 안되는 길이
    int len = end - start + 1;
    // 기지국 1개의 전파 범위
    int range = (w*2)+1;
    // 기지국 개수
    int cnt = 0;
    while (cnt*range < len) {
        cnt += 1;
    }
    return cnt;
}
 
int solution(int n, vector<int> stations, int w) {
    int answer = 0;
    // 1번 째 기지국 왼쪽에 추가 설치해야 하는 개수
    if (stations[0]-w-1 >= 1) {
        answer += cal(1, stations[0]-w-1, w);
    }
    // 기지국과 기지국 사이에 추가로 설치해야 하는 개수
    for (int i = 1; i < stations.size(); i++) {
        answer += cal(stations[i-1]+w+1, stations[i]-w-1, w);
    }
    // 마지막 기지국 오른쪽에 추가로 설치해야 하는 개수
    if (stations.back()+w+1 <= n) {
        answer += cal(stations.back()+w+1, n, w);
    }
    return answer;
}