프로그래머스 - 기지국 설치

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

프로그래머스

---

문제 설명

4G 기지국을 5G 기지국으로 모두 바꿀 예정입니다. 하지만 5G 기지국이 4G 기지국보다 전달 범위가 좁아, 어떤 아파트에는 전파가 도달하지 않는 문제가 생겼습니다.

쭉 늘어서있는 아파트 개수 n개와 기존 4G 기지국 위치가 담겨있는 배열 stations, 5G 기지국의 전파 전달 범위 w가 주어질 때, 모든 아파트에 전파를 전달하기 위한 최소 추가 5G 기지국 개수를 구하시오.

N : 2억 이하의 자연수
stations : 1만 이하의 자연수. 오름차 순으로 정렬되어 있습니다.
W : 1만 이하의 자연수

---

아이디어

● 아파트가 최대 2억이기 때문에 기지국에 초점을 맞춰 문제 풀이해야 할 것 같습니다.

● 기지국이 없는 구역을 구해 해당 구역에 기지국이 몇개 들어가는지 확인해서 더합니다.

● 1에서 시작해 n까지 아파트가 있어서 기지국이 사이사이 기지국 없는 구역을 구할 때 숫자에 조심해야할 것 같습니다...

---

코드

#include <bits/stdc++.h>

using namespace std;

int CreateStation(int betweenArea, int w)
{
    if(betweenArea <= 0) return 0;
    int ret = betweenArea / w ;
    if((betweenArea % w) != 0) ++ret;
    return ret;
}

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    for(int i = 1; i < stations.size(); ++i)
    {
        int prevStation = stations[i-1];
        int curStation = stations[i];
        int betweenArea = (curStation - w -(prevStation + w) - 1);
        answer += CreateStation(betweenArea, w*2+1);
    }
    answer += CreateStation((stations.front() - w - 1), w*2+1);
    answer += CreateStation(n - (stations.back() + w), w*2+1);
    return answer;
}

메모리 3.96MB, 시간 0.12ms

---