(C++) - 프로그래머스(Summer/Winter Coding(~2018)) : 기지국 설치

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

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

그리디 문제였습니다.

 

풀이방법

아파트의 개수가 최대 2억이기 때문에 배열로 체크하는 형식은 불가합니다. 따라서 회색 부분의 길이들을 모두 구해서  저장한 뒤 순차적으로 기지국을 설치해줘야합니다. 

 

1. 영역 구하기

 회색 부분의 영역은 3가지 형태로 존재합니다.

 1-1. 가장 왼쪽 영역 : 이 경우에는 1번 아파트 부터 처음 설치된 기지국까지의 길이에서 기지국이 w만큼 왼편에 전파를 전달할 수 있으므로 stations[0] - w - 1의 길이를 가집니다.

 

 1-2. 이미 설치된 기지국 사이에 있는 영역 : 상기 이미지를 토대로 설명하면 이 사이에서 전파가 닿는 거리는 4번 아파트에 설치된 기지국의 오른편, 11번 아파트에 설치된 기지국의 왼편이므로 회색영역의 길이는 11 - 4 - w*2 - 1입니다.

 

 1-3. 가장 오른쪽 영역

이 구역은 상기 맥락으로 n - 마지막으로 설치된 기지국 위치 - w가 됩니다.

 

2. 저장

 이렇게 3가지로 나뉜 영역들의 길이를 모두 구해 emptySpaces라는 vector 변수에 저장합니다.

 

3. 정답 출력

 하나의 기지국은 w * 2 + 1만큼의 길이를 커버할 수 있습니다. 최대한 겹치지 않게 설치하려면 빈 영역 하나의 길이 / 한 기지국이 커버할 수 있는 길이의 합이 정답이 됩니다. 여기서 주의할 점은 나누어 떨어진다면 딱 맞게 더하면 되지만 만약 나머지가 남는다면 + 1 하는식으로 빈 영역당 설치해야할 기지국의 개수를 구합니다.

 

 

 

Code

#include <bits/stdc++.h>
using namespace std;

int solution(int n, vector<int> stations, int w){
    vector <int> emptySpaces;
    int size = stations.size();
    int ans = 0;

    int space = stations[0] - w - 1;
    emptySpaces.push_back(space);

    for(int i = 1; i < size; i++){
        space = stations[i] - stations[i-1] - 1 - w * 2;
        emptySpaces.push_back(space);
    }

    space = n - stations[size - 1] - w;
    emptySpaces.push_back(space);

    int coverLength = w * 2 + 1;
    for(auto e : emptySpaces) {
        if(e <= 0) continue;
        if(e %  coverLength) ans += e/coverLength + 1;
        else ans += e/coverLength;
    }

    return ans;
}