[Programmers, C++]#Level3_기지국 설치

#1. 문제

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

 

---

 

#2. 풀이

 

1. 마지막 최대 범위 기억하고, 커버하지 못한 영역에 대한 처리!

1. 먼저, 현재 기지국이 커버 가능한 범위의 최소 값과 최대 값을 찾습니다.
2. 이전 기지국이 커버한 최대 값과 현재 기지국 범위의 최소 값을 비교하고, 아직 커버하지 못한 영역이 존재한다면 " (uncoveredLength + 2*w) / (2*w + 1)" 만큼 기지국을 증설해 줍니다. 그리고, 마지막 커버한 최대 값을 현재 기지국 범위의 최대 값으로 업데이트해줍니다.
3. 모든 작업을 마치고, 마지막 기지국 이후 커버하지 못하고 남은 영역에 대한 추가적인 처리 이후, 증설할 기지국 개수를 반환해 줍니다.

 

---

 

#3. 코드

/*
    @문제: 기지국의 전파 범위 변경으로, 기존의 아파트 중 전파를 전달 받지 못하는 아파트들을 위해 필요한 최소한의 추가 기지국 갯수
    @설명
        1. 기지국 위치의 왼쪽 경계와 오른쪽 경계 찾고, 오른쪽 경계를 기억한다.
        2. 왼쪽 경계보다 왼쪽에 있는 아파트들 중 전파 도달 범위 밖에 있는 아파트 갯수를 통해 추가 증설 기지국 갯수 계산
        4. 마지막 기지국의 오른쪽 경계보다 오른쪽에 있는 아파트 갯수를 통해 추가 증설 기지국 갯수 계산
        * 스택 활용으로 뻘짓함
*/

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

int solution(int n, vector<int> stations, int w) {
    int answer = 0;
    int lastCovered = 0;
    for(int i = 0; i < stations.size(); ++i) {
        // 현재 기지국이 커버하는 최소, 최대 범위 계산
        int start = stations[i] - w;
        int end = stations[i] + w;
        
        // 아직 커버되지 않은 영역 계산
        if(lastCovered < start - 1) {
            // 필요한 기지국 수 계산
            int uncoveredLength = start - lastCovered - 1;
            answer += (uncoveredLength + 2*w) / (2*w + 1);
        }
        
        // 마지막 커버된 위치 갱신
        lastCovered = end;
    }
    
    // 마지막 기지국 이후 남은 영역에 대해 처리
    if(lastCovered < n) {
        int uncoveredLength = n - lastCovered;
        answer += (uncoveredLength + 2*w) / (2*w + 1);
    }
    
    return answer;
}

 

---