[프로그래머스] 12979. 기지국 설치 (C++)

코딩테스트 연습 - 기지국 설치

문제 설명

1. 5g가 도달하지 않는 곳에 기지국 설치

2. 최소로 설치할 수 있는 기지국의 개수 출력

 

풀이

1. N <= 200,000,000 이므로 모든 아파트의 기지국 설치 여부를 판단하는 건 X.. 

2. 이미 설치된 기지국을 확인하면서, 기지국 좌우로 전파가 전달되지 않는 영역 확인

3. 연속된 전파가 전달되지 않는 영역을 하나의 그룹으로 생각 ex. 1-2, 6-9

4. 그룹의 크기를 알면 그 그룹에 몇 개의 기지국이 필요한 지 알 수 있음! -> answer에 더해주기

 

코드

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

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

    return answer;
}