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

문제 링크

기지국 설치

풀이

구현 문제

초기화 된 모습

1. 전파가 안들어오는 곳의 개수를 세서 전파 범위를 나누어주면 된다.
2. 개수를 세기 위해 현재 아파트의 인덱스 idx와 현재 전파가 들어오는 아파트(i)의 범위 첫번째 stt, 마지막 end 변수 선언
   2-1. idx는 1번째 아파트부터 세야 하니 1,
   stt는 stations[i]-w, end는 stations[i]+w가 된다.
   2-2. cnt는 전파가 안들어오는 아파트의 개수인데 stt-idx 값이고,
   개수를 범위로 나누었을 때 나누어 떨어지면 나눈 값, 나누어 떨어지지 않으면 나눈 값의 +1을 해준다.
   여기서 if(idx<stt)를 해준 이유는, idx가 1번째 아파트부터 시작하는데, 전파가 들어오는 아파트 범위가 1번째일 경우나, 범위가 겹치는 경우에는 해당 값을 계산하면 안되기 때문에(다음에 계산해야 하기 때문에) 체크해준다.
   2-3. 다음 번의 체크해야 할 범위는 end+1가 되니 갱신해준다.
3. 2번을 끝냈는데도 계산해야 할 아파트들이 남아있다면(맨 뒷 부분) 한 번 더 계산해준다.(문제의 두번째 예와 같이)
   이것의 체크는 if(idx<=n)으로 체크하는데, 현재 체크하는 아파트가 아파트의 개수보다 작거나 같으면임
   3-1. 바로 cnt를 구해서 2-2와 같게 계산한다.

코드

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

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

    int idx = 1;
    for(int i=0;i<stations.size();i++)
    {
        int stt = stations[i]-w;
        int end = stations[i]+w;
        if(idx<stt)
        {
            int cnt = stt-idx;
            if(cnt%(w*2+1)==0) answer += cnt/(w*2+1);
            else answer += cnt/(w*2+1) + 1;
        }
        idx = end+1;
    }
    
    if(idx<=n) 
    {
        int cnt = n-idx+1;
        if(cnt%(w*2+1)==0) answer += cnt/(w*2+1);
        else answer += cnt/(w*2+1) + 1;
    }

    return answer;
}